2
\$\begingroup\$

I gave an attempt at reinventing the wheel and recreate list methods using my own Array Class to broaden my understanding about lists. I would like advice regarding efficiency, and in implementing negative indexes, since my code only works for positive ones.

class Array:

    def __init__(self, List=[]):
        self.array = List

    def display(self):
        print(self.array)

    def len(self):
        array = self.array
        count = 0
        for _ in array:
            count += 1
        return count

    def append(self, value):
        array = self.array
        length = self.len()
        results = [None] * (length+1)
        for i in range(length):
            results[i] = array[i]
        results[length] = value
        self.array = results

    def search(self, value):
        array = self.array
        pos = -1
        for index in range(self.len()):
            if array[index] == value:
                pos = index
        return pos

    def insert(self, index, value):
        array = self.array
        length = self.len()
        results = [None] * (length+1)
        if index > length:
            raise IndexError
        elif index == length:
            self.append(value)
            results = self.array
        else:
            for i in range(length):
                if i == index:
                    for j in range(index + 1, length + 1):
                        results[j] = array[j-1]
                    results[index] = value
                    break
                else:
                    results[i] = array[i]
        self.array = results

    def delete(self, value):
        array = self.array
        length = self.len()
        results = [None] * (length-1)
        pos = self.search(value)
        if pos == -1:
            raise "Index Error: Element Not Found"
        else:
            for i in range(length):
                if i != pos:
                    results[i] = array[i]
                else:
                    for j in range(pos+1, length):
                        results[j-1] = array[j]
                    break
        self.array = results

    def pop(self):
        array = self.array
        length = self.len()
        results = [None] * (length-1)
        if length == 0:
            raise IndexError

        value = array[-1]
        for i in range(length-1):
            results[i] = array[i]
        self.array = results
        return value
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Seems like cheating to re-implement a list using a list... I feel like the real challenge would be doing so without a list of any sort, say creating a linked list or a tree or something like that. That might be pedantic, but it'd clarify what your limitation are and thus what efficient solutions are available versus what you're making needlessly hard for yourself because it's fun.

Most of your functions are going to be very expensive because you're constantly copying memory around. A more common approach is to over-allocate space and then keep two values, "length" and "_allocated". The first is how many valid elements your array contains; the second is how much space you've reserved to store values. When you want to append X to your array, you can just assign X to self.array[self.length] and then increment self.length. If that would take you beyond what you've allocated, only then you do the expensive act of allocating a new chunk of memory (in your case, the [None] * (length + 1) line) and copying the data. To minimize the number of copies, it's common practice to double the length of the array each time you resize it (maybe up to some maximum, at which point you add on new 4K element blocks or whatever rather than multiplying, to prevent running out of memory prematurely). When inserting, then, you'd just need to shift the later values rather than copy everything; similarly, when popping values off, just decrement self.length to mark that last element as unimportant and available to be overwritten.

To complement that approach, if you want to optimize for mid-array insertions and deletions, you can maintain a parallel bit-array of which values are valid and which aren't. Iterating through the array becomes trickier (you need to zip the values with the validity flags and only return the valid ones), but deleting an item becomes cheaper since you only need to find the element and mark it as deleted (no shifting required), and inserting an item only requires shifting things until you find an unused element that can be overwritten instead of shifted.

Caching the length of the array is a good idea in general (though not necessary if you don't over-allocate). It requires extra code and care to keep synchronized with the rest of the array, but checking a list's length is a very common thing for users to want to do, and the O(N) computation each time can get painful.

As a general Python'ism, I'd say use def __len__ instead of def len and implement __get_item__, as well as any other magic methods that generally correspond to an array. For reference see this documentation page, and consider that most people think of an array as some combination of a "Collection" and "[Mutable]Sequence"

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.