Skip to main content
Computer Science

Return to Question

added 323 characters in body
Source Link
Herman Autore
Herman Autore
  • 13
  • 5
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 
names := empty list  
for rowline in listproteins:  
|    name := first element in row"line"  
|   if namefor notprot in namesprots:  
|    |   append if prot in name:  
|    |    |    append alias to namesD_{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 thousandmillion 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?

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

However, this approach is extremely slow. Even running this on only 10 thousand 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?

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?

Better formatting
Source Link
Herman Autore
Herman Autore
  • 13
  • 5

I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ isand $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.:

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

names := empty list
for row in list:
____name := first element in row
____if name not in names:
________append name to names

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

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

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

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

names := empty list
for row in list:
____name := first element in row
____if name not in names:
________append name to names

I know for a fact that there are only 10 million unique values.

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.:

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

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

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

Source Link
Herman Autore
Herman Autore
  • 13
  • 5

What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?

#Background#

I have a list of 50 million $A-A_i$ pairs, where $i>1$ and $A$ is 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
____if name not in names:
________append name to names

However, this approach is extremely slow. Even running this on only 10 thousand 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.

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

Thank you