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$
  • $\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

Your Answer

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

Browse other questions tagged or ask your own question.