You can click on the wheel in the top-left corner to go back to the Home page. You probably figured that out by yourself. I'm just trying to be nice.
Before we begin: If you'd like to get a working file containing this implementation for some reason,
you can simply use curl to download it, like so:
curl https://fmonti.neocities.org/res/array-collection.txt >> array-collection.py
This is a small and somewhat inefficient data structure for storing multiple arrays in the same memory location.
I say inefficient, because massive amounts of space within the array are left empty until the maximum amount of arrays have been stored; then, all indices are filled.
The data structure uses prime numbers as base indices, where each prime represents one array. Upon reading and writing data, the prime base index is then bitshifted until the desired location has been reached.
The implementation below is somewhat rudimentary and written in Python, since that seems to be the popular language for proof-of-concepts like this right now.
class ArrayCollection: # Create a new ArrayCollection of the given size: def __init__(self, size): self.arr = [None for _ in range(size)] self.ptr = 1 # Insert a value at end of the given array: def insert(self, tpl): # tpl is a tuple self.ptr = primeByIndex(tpl) while self.arr[self.ptr] is not None: self.ptr = self.ptr << 1 self.arr[self.ptr] = tpl # Remove the last element from the given array def remove(self, arr): self.ptr = primeByIndex(arr) while self.arr[self.ptr] is not None: self.ptr = self.ptr << 1 self.arr[self.ptr >> 1] = None # Get a value at the given index, from the given array: def get(self, tpl): self.ptr = primeByIndex(tpl) self.ptr = self.ptr << tpl return self.arr[self.ptr]
This class can then be used like so:
# Example Usage: collection = ArrayCollection(100) collection.insert((0, "Hello")) collection.insert((0, "World!")) collection.insert((1, "Bye")) collection.insert((1, "World!")) print(collection.get((1, 1))) # Will print "World!" print(collection.get((0, 0))) # Will print "Hello"
The implementation only supports appending to, and removing from the end of the array. It's also fixed in maximum capacity; a proper implementation would provide a method for resizing. A proper implementation would also replace the inefficient prime functions that are used here for sake of simplicity:
def isPrime(x): if x <= 2: return True for i in range(2, x): if x % i == 0: return False return True def primeByIndex(index): cnt = 2 for i in range(index): cnt = nextPrime(cnt) return cnt def nextPrime(x): if x <= 2: return x + 1 for i in range(x + 1, x + 100): if isPrime(i): return i raise Exception("Could not find next prime")
And that's basically it! If this data structure/algorithm already exists by another name, please let me know. I came up with this during a challenge I thought up: "One Algorithm A Day". I didn't keep it up, but I kinda want to attempt it again.