1
$\begingroup$

Background

I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.:

$$ \text{New List}= \{A, B, C, ...\} $$

Here is a generic illustration of what the list of pairs looks like:

list of pairs = [['A', 'A1'],
                 ['A', 'A2'],
                 ['A', 'A3'],
                 ['B', 'B1'],
                 ['C', 'C1'],
                  ...

Here is some actual data:

`['394.NGR_c13430',
  '(3R)-hydroxymyristoyl-[acyl-carrier-protein] dehydratase'],`  
`['394.NGR_c31790',
  '(Di)nucleoside polyphosphate hydrolase'],`  
`['394.NGR_c00410',
  '(Dimethylallyl)adenosine tRNA methylthiotransferase MiaB'],`  
`['394.NGR_c28950',
  '1,4-alpha-D-glucan:1,4-alpha-D-glucan 6-glucosyl-transferase'],`  
`['394.NGR_c28950',
  '1,4-alpha-glucan branching enzyme GlgB'],`  
`['394.NGR_c34010', '1-(5-phosphoribosyl)-5-[(5-ph']]`  
`    9606.ENSP00000170630   1IAR`  
`    9606.ENSP00000170630   1ITE`  
`    9606.ENSP00000170630   287261`  
`    9606.ENSP00000170630   287263`  
`    9606.ENSP00000170630   287265`  
`    9606.ENSP00000170630   287267`  
`    9606.ENSP00000170630   287269`  
`    9606.ENSP00000170630   287271`  
`    9606.ENSP00000170630   3566`  

(Sorry for the sloppy formatting, but I hope you get the idea.)

My Attempt

I'm doing:

names := empty list
for row in list:
| name := first element in row
| for name in names: | | if name not in names:
| | | append name to names

for line in proteins:  
|    name := first element in "line"  
|    for prot in prots:  
|    |    if prot in name:  
|    |    |    append alias to D_{prot}  

Where D_{prot} is $D_{prot}$, a sublist in D containing the $A_{i's}$ of prot.

However, this approach is extremely slow. Even running this on only 10 million of the pairs takes more than half an hour. I'm only a statistician and not familiar with the intricacies of computer science or Python. Is there a better way of doing this?

Also...

I know for a fact that there are only 10 million unique values ($A$ values).

With $n$ = 50 million and $p$ = 10 million, I thought my algorithm was $O(np)$. Is it? Is this efficient?

Thank you

$\endgroup$
3
  • $\begingroup$ Use a hash table instead of a dynamic array to store the names. Look into Python's set. $\endgroup$ – Mike Borkland Sep 11 '18 at 23:48
  • $\begingroup$ So in Python a list object is a dynamic array, while a dictionary is a hash table? Do Python sets also work as hash tables? $\endgroup$ – Herman Autore Sep 12 '18 at 4:46
  • $\begingroup$ Yes, that's correct. $\endgroup$ – Mike Borkland Sep 12 '18 at 9:57
0
$\begingroup$

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. n test

Here is a plot of p with constant n of 1 million and the time it takes to process on the vertical axis. p test

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. n test with both methods

p test with both methods

Since the orange line is a little difficult to see, here is a rerun with only the dict method. p test with dict method only

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()
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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