9

I got a list of objects which look like strings, but are not real strings (think about mmap'ed files). Like this:

x = [ "abc", "defgh", "ij" ]

What i want is x to be directly indexable like it was a big string, i.e.:

(x[4] == "e") is True

(Of course I don't want to do "".join(x) which would merge all strings, because reading a string is too expensive in my case. Remember it's mmap'ed files.).

This is easy if you iterate over the entire list, but it seems to be O(n). So I've implemented __getitem__ more efficiently by creating such a list:

x = [ (0, "abc"), (3, "defgh"), (8, "ij") ]

Therefore I can do a binary search in __getitem__ to quickly find the tuple with the right data and then indexing its string. This works quite well.

I see how to implement __setitem__, but it seems so boring, I'm wondering if there's not something that already does that.

To be more precise, this is how the data structure should honor __setitem__:

>>> x = [ "abc", "defgh", "ij" ]
>>> x[2:10] = "12345678"
>>> x
[ "ab", "12345678", "j" ]

I'd take any idea about such a data structure implementation, name or any hint.

Improve this question
9
  • 2
    "Of course I don't want to do "".join(x) which would merge all strings?" Why not? "reading a string is too expensive in my case" What does that have to do with anything? What -- exactly -- is wrong with the join? Commented May 26, 2011 at 15:52
  • Because the strings in the list are not really strings. They are (sort of) mmap'ed files. But they just work like strings (they implement __getitem__). Commented May 26, 2011 at 16:00
  • x[4] == e because __getitem__ is overloaded in x class (a subclass of list). Commented May 26, 2011 at 16:13
  • @Woot4Moo: If you joined all the strings together into one, 'e' is at index 4. Commented May 26, 2011 at 16:19
  • 1
    @jd_: "the strings in the list are not really strings". Then please fix the question to state what the really are. Right now, the question is misleading. Commented May 26, 2011 at 18:18

5 Answers 5

Reset to default
9

What you are describing is a special case of the rope data structure.

Unfortunately, I am not aware of any Python implementations.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for the link! Indeed, it really looks like it. :)
PyPy implements the rope data structure does it not? - morepypy.blogspot.com/2007/11/ropes-branch-merged.html
0

So do you still want to be able to address the n'th list element at all, like find that x.somemethod(2) == 'ij'? If not, then your data structure is just a string with some methods to make it mutable and to initialize it from a list of strings.

If you do want to be able to, then your data structure is still a string with those extra methods, plus another element to track the ranges where its elements came from, like x.camefrom(1) == (3, 7).

Either way, it appears that you want to be storing and manipulating a string.

Improve this answer

2 Comments

You missed the part where I wrote "I don't want to read the string". If I understand you correctly, creating a string initialized from a list of string means reading all the strings and copying them. :)
I didn't miss it. I ignored it because it sounded like you're making things a lot harder than you need to, without explaining why you want to do it the hard way. :-)
0

This could be a start:

self._h = {0:"abc", 3:"defgh", 8:"ij"} #create _h and __len__ in __init__
self.__len__ = 10

def __getitem__(i):
    if i >= self.__len__:
        raise IndexError
    o=0
    while True:
        if i-o in self._h:
            return self._h[i-o][o]
        o+=1

improvements contain mutability.

Improve this answer

Comments

0

I'm not aware of anything that does what you want.

However, if you've implemented __getitem__ efficiently the way you say, then you already have the code that maps an index to your tuple, string list. Therefore it seems like you could just reuse that bit of code -- with a little refactoring -- to implement __setitem__ which needs the same information to perform its function.

Improve this answer

Comments

-1

You have recreated the dictionary data type.

Improve this answer

9 Comments

Not exactly. In a dictionary, you cannot trivially find the character at position i if i is not the start of one of the substrings.
Not every key corresponds directly to one the strings in his list. If you mean it's conceptually a dictionary, that's not true either since there can be no i between 0 and len(op_s_object) s.t. op_s_object[i] has no value.
The op's explanation is lacking something, for instance he has yet to explain how x[4] == e. Is he overriding equals to mean contains:?
"What i want is x to be directly indexable like it is a big string" -- I take this to mean he's building a sequence type, i.e. a string by different means.
why not just use a character array which already has O(1) lookup. Or perhaps its O(n) I forget.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.