Question 1: How to solve the finding uniques problem
If your data is consistently formatted in this way:
[
['somestring', 'someotherstring'],
['anotherstring', 'anotherotherstring'],
]
And so on, you can actually just call dict directly on it and it will reduce all of the first items to keys, and keep the last of the second items as the values, and this runs extremely quickly. You can then retrieve the keys from the dictionary to get your unique list.
Here is an example:
a = [
['somestring', 'someotherstring'],
['anotherstring', 'anotherotherstring'],
]
b = dict(a)
print(list(b.keys()))
I tested this with a data set resembling the one you describe, with 50 million entries and 10 million unique values. On a single core in my laptop it took only about 15 seconds to run and used about 5.5 GB of memory. It actually took 10 times as long to make the data as it did to reduce it to a unique list. I have included the code I used to test below:
import random
import string
import time
def make_data(n, min_len, max_len, repeat_chance=0.0):
dataset = []
for i in range(n):
if random.random() < repeat_chance and len(dataset) > 1:
dataset.append([random.choice(dataset)[0], ''])
else:
key = ''.join(random.choices(string.printable, k=random.randint(min_len, max_len)))
dataset.append([key, ''])
return dataset
def main():
random.seed(42) # For reproducibility
start_time = time.time()
x = make_data(50000000, 10, 100, 0.8) # 50 M with 80% repeats for ~10 M unique
mid_time = time.time()
y = dict(x) # Reduce to unique keys
end_time = time.time()
print('Make data: {0:.2f} s'.format(mid_time - start_time))
print('Make dict: {0:.2f} s'.format(end_time - mid_time))
print('Total time: {0:.2f} s'.format(end_time - start_time))
print('Total items: ', len(x))
print('Unique items: ', len(y))
if __name__ == '__main__':
main()
And got the following output which is consistent with the specifications of 50 million entries and 10 million unique values
Make data: 169.61 s
Make dict: 15.47 s
Total time: 185.08 s
Total items: 50000000
Unique items: 10000776
Question 2: What is the complexity of that algorithm?
Is adding p unique values to a list and then searching the list for each new value from a list of n values to determine if its unique a O(np) problem?
Intuitively, I expect this to be a O(np2) problem. As n goes up, we must go through each one only once, so linear in n. As p goes up, we must go through more uniques to tell if the new value coming in is unique, so p2. This wiki page has almost exactly this situation, and shows how to derive the O(n2) complexity. But let's not let intuition guess for us, lets do the work.
Here is a plot of n with constant-ish p of 5000 and the time it takes to process it using your algorithm on the vertical axis.
Here is a plot of p with constant n of 1 million and the time it takes to process on the vertical axis.
These plots suggest that the list algorithm offers the complexity we expected of O(np2).
Bonus Question: How does the dict method compare to the list method?
Just for the intrigue, I also compared the dict method to your list algorithm and plotted them together. Blue is the list algorithm, and orange is the dict method.
Since the orange line is a little difficult to see, here is a rerun with only the dict method.
As you can see, the dict method maintains linear performance with respect to p, offering an overall performance of O(np) while the list algorithm offers the complexity we expected of O(np2). The dict method also outperformed the list algorithm at every test point.
If anyone is so inclined, here is the code used to generate that data.
import random
import string
import time
import matplotlib.pyplot as plot
def make_data(n, min_len, max_len, repeat_chance=0.0):
dataset = []
for i in range(n):
if random.random() < repeat_chance and len(dataset) > 1:
dataset.append([random.choice(dataset)[0], ''])
else:
key = ''.join(random.choices(string.printable, k=random.randint(min_len, max_len)))
dataset.append([key, ''])
return dataset
def get_uniques_listwise(dataset):
uniqueset = []
for datapoint in dataset:
if not datapoint[0] in uniqueset:
uniqueset.append(datapoint[0])
return uniqueset
def get_uniques_dict(dataset):
return list(dict(dataset).keys())
def makechart(testpoints, index, xlabel, ylabel, title, f0, f1=None):
n_times0 = []
n_times1 = []
for testpoint in testpoints:
dataset = make_data(testpoint[0], 10, 100, 1 - testpoint[1] / testpoint[0])
start_time = time.time()
f0(dataset)
end_time = time.time()
n_times0.append(end_time - start_time)
if not f1 is None:
start_time = time.time()
f1(dataset)
end_time = time.time()
n_times1.append(end_time - start_time)
plot.plot([x[index] for x in testpoints], n_times0)
if not f1 is None:
plot.plot([x[index] for x in testpoints], n_times1)
plot.xlabel(xlabel)
plot.ylabel(ylabel)
plot.title(title)
plot.show()
def main():
random.seed(42) # For reproducibility
n_p_testpoints_n = [
[100000, 5000],
[500000, 5000],
[1000000, 5000],
[2000000, 5000],
[5000000, 5000],
[7000000, 5000],
[8000000, 5000],
[9000000, 5000],
[10000000, 5000]
]
makechart(
n_p_testpoints_n,
0,
'n',
'time to find uniques',
'varying n with near constant p=5000',
get_uniques_listwise,
get_uniques_dict
)
random.seed(42) # For reproducibility
n_p_testpoints_p = [
[1000000, 10000],
[1000000, 15000],
[1000000, 20000],
[1000000, 25000],
[1000000, 30000],
[1000000, 35000],
[1000000, 40000],
[1000000, 45000],
[1000000, 50000],
]
makechart(
n_p_testpoints_p,
1,
'p',
'time to find uniques',
'varying p with constant n=1000000',
get_uniques_listwise,
get_uniques_dict
)
if __name__ == '__main__':
main()
set. $\endgroup$