Code Snippets – Broken Things

Array Collection Algoritm

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[0])
 
        while self.arr[self.ptr] is not None:
            self.ptr = self.ptr << 1
 
        self.arr[self.ptr] = tpl[1]
    
    # 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[0])
        self.ptr = self.ptr << tpl[1]
 
        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.