Mailing List Archive: Python: Python

finding most common elements between thousands of multiple arrays.

1 2

View All

Index | Next | Previous | View Threaded

hanooter at gmail

Jul 4, 2009, 12:33 AM

Post #1 of 27 (1232 views)
Permalink

finding most common elements between thousands of multiple arrays.

Currently I need to find the most common elements in thousands of
arrays within one large array (arround 2 million instances with ~70k
unique elements)

so I set up a dictionary to handle the counting so when I am
iterating I up the count on the corrosponding dictionary element. I
then iterate through the dictionary and find the 25 most common
elements.

the elements are initially held in a array within an array. so I am am
just trying to find the most common elements between all the arrays
contained in one large array.
my current code looks something like this:
d = {}
for arr in my_array:
-----for i in arr:
#elements are numpy integers and thus are not accepted as dictionary
keys
-----------d[int(i)]=d.get(int(i),0)+1

then I filter things down. but with my algorithm that only takes about
1 sec so I dont need to show it here since that isnt the problem.

But there has to be something better. I have to do this many many
times and it seems silly to iterate through 2 million things just to
get 25. The element IDs are integers and are currently being held in
numpy arrays in a larger array. this ID is what makes up the key to
the dictionary.

It currently takes about 5 seconds to accomplish this with my current
algorithm.

So does anyone know the best solution or algorithm? I think the trick
lies in matrix intersections but I do not know.
--
http://mail.python.org/mailman/listinfo/python-list

clp2 at rebertia

Jul 4, 2009, 12:45 AM

Post #2 of 27 (1197 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Sat, Jul 4, 2009 at 12:33 AM, mclovin<hanooter [at] gmail> wrote:
> Currently I need to find the most common elements in thousands of
> arrays within one large array (arround 2 million instances with ~70k
> unique elements)
>
> so I set up a dictionary to handle the counting so when I am
> iterating I up the count on the corrosponding dictionary element. I
> then iterate through the dictionary and find the 25 most common
> elements.
>
> the elements are initially held in a array within an array. so I am am
> just trying to find the most common elements between all the arrays
> contained in one large array.
> my current code looks something like this:
> d = {}
> for arr in my_array:
> -----for i in arr:
> #elements are numpy integers and thus are not accepted as dictionary
> keys
> -----------d[int(i)]=d.get(int(i),0)+1
>
> then I filter things down. but with my algorithm that only takes about
> 1 sec so I dont need to show it here since that isnt the problem.
>
>
> But there has to be something better. I have to do this many many
> times and it seems silly to iterate through 2 million things just to
> get 25. The element IDs are integers and are currently being held in
> numpy arrays in a larger array. this ID is what makes up the key to
> the dictionary.
>
> It currently takes about 5 seconds to accomplish this with my current
> algorithm.
>
> So does anyone know the best solution or algorithm? I think the trick
> lies in matrix intersections but I do not know.

Using a defaultdict
(http://docs.python.org/library/collections.html#collections.defaultdict)
would speed it up (but only slightly) and make it clearer to read.

Cheers,
Chris
--
http://blog.rebertia.com
--
http://mail.python.org/mailman/listinfo/python-list

andreengels at gmail

Jul 4, 2009, 1:04 AM

Post #3 of 27 (1200 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Sat, Jul 4, 2009 at 9:33 AM, mclovin<hanooter [at] gmail> wrote:
> Currently I need to find the most common elements in thousands of
> arrays within one large array (arround 2 million instances with ~70k
> unique elements)
>
> so I set up a dictionary to handle the counting so when I am
> iterating I up the count on the corrosponding dictionary element. I
> then iterate through the dictionary and find the 25 most common
> elements.
>
> the elements are initially held in a array within an array. so I am am
> just trying to find the most common elements between all the arrays
> contained in one large array.
> my current code looks something like this:
> d = {}
> for arr in my_array:
> -----for i in arr:
> #elements are numpy integers and thus are not accepted as dictionary
> keys
> -----------d[int(i)]=d.get(int(i),0)+1
>
> then I filter things down. but with my algorithm that only takes about
> 1 sec so I dont need to show it here since that isnt the problem.
>
>
> But there has to be something better. I have to do this many many
> times and it seems silly to iterate through 2 million things just to
> get 25. The element IDs are integers and are currently being held in
> numpy arrays in a larger array. this ID is what makes up the key to
> the dictionary.
>
> It currently takes about 5 seconds to accomplish this with my current
> algorithm.
>
> So does anyone know the best solution or algorithm? I think the trick
> lies in matrix intersections but I do not know.

There's no better algorithm for the general case. No method of
checking the matrices using less than 2000000-x look-ups will ensure
you that there's not a new value with x occurences lurking somewhere.

However, if you need this information more often, and if the number of
values that changes in between is small compared to the total size of
the matrices, you could make a gain in subsequent calculations by
remembering part results. Depending on the situation you could for
example keep the dictionary with the counts and update it each time,
or keep such a dictionary for each "big" matrix, and set a flag when
that dictionary is not up-to-date any more

.

--
André Engels, andreengels [at] gmail
--
http://mail.python.org/mailman/listinfo/python-list

vilya.harvey at gmail

Jul 4, 2009, 2:55 AM

Post #4 of 27 (1202 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

2009/7/4 Andre Engels <andreengels [at] gmail>:
> On Sat, Jul 4, 2009 at 9:33 AM, mclovin<hanooter [at] gmail> wrote:
>> Currently I need to find the most common elements in thousands of
>> arrays within one large array (arround 2 million instances with ~70k
>> unique elements)
>>
>> so I set up a dictionary to handle the counting so when I am
>> iterating �I up the count on the corrosponding dictionary element. I
>> then iterate through the dictionary and find the 25 most common
>> elements.
>>
>> the elements are initially held in a array within an array. so I am am
>> just trying to find the most common elements between all the arrays
>> contained in one large array.
>> my current code looks something like this:
>> d = {}
>> for arr in my_array:
>> -----for i in arr:
>> #elements are numpy integers and thus are not accepted as dictionary
>> keys
>> -----------d[int(i)]=d.get(int(i),0)+1
>>
>> then I filter things down. but with my algorithm that only takes about
>> 1 sec so I dont need to show it here since that isnt the problem.
>>
>>
>> But there has to be something better. I have to do this many many
>> times and it seems silly to iterate through 2 million things just to
>> get 25. The element IDs are integers and are currently being held in
>> numpy arrays in a larger array. this ID is what makes up the key to
>> the dictionary.
>>
>> �It currently takes about 5 seconds to accomplish this with my current
>> algorithm.
>>
>> So does anyone know the best solution or algorithm? I think the trick
>> lies in matrix intersections but I do not know.
>
> There's no better algorithm for the general case. No method of
> checking the matrices using less than 2000000-x look-ups will ensure
> you that there's not a new value with x occurences lurking somewhere.

Try flattening the arrays into a single large array & sorting it. Then
you can just iterate over the large array counting as you go; you only
ever have to insert into the dict once for each value and there's no
lookups in the dict. I don't know numpy, so there's probably a more
efficient way to write this, but this should show what I'm talking
about:

big_arr = sorted(reduce(list.__add__, my_array, []))
counts = {}
last_val = big_arr[0]
count = 0
for val in big_arr:
if val == last_val:
count += 1
else:
counts[last_val] = count
count = 0
last_val = val
counts[last_val] = count # to get the count for the last value.

If flattening the arrays isn't practical, you may still get some
improvements by sorting them individually and applying the same
principle to each of them:

counts = {}
for arr in my_array:
sorted_arr = sorted(arr)
last_val = sorted_arr[0]
count = 0
for val in sorted_arr:
if val == last_val:
count += 1
else:
counts[last_val] = counts.get(last_val, 0) + count
count = 0
last_val = val
counts[last_val] = counts.get(last_val, 0) + count

Hope that helps...

Vil.
--
http://mail.python.org/mailman/listinfo/python-list

neilcrighton at gmail

Jul 4, 2009, 6:39 AM

Post #5 of 27 (1194 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

You can join all your arrays into a single big array with concatenate.

>>> import numpy as np
>>> a = np.concatenate(array_of_arrays)

Then count the number of occurrances of each unique element using this trick
with searchsorted. This should be pretty fast.

>>> a.sort()
>>> unique_a = np.unique(a)
>>> count = []
>>> for val in unique_a:
... count.append(a.searchsorted(val,side='right') - a.searchsorted(val,
side='left'))
>>> mostcommonvals = unique_a[np.argsort(count)[-25:]]

Neil

--
http://mail.python.org/mailman/listinfo/python-list

steve at REMOVE-THIS-cybersource

Jul 4, 2009, 6:42 AM

Post #6 of 27 (1182 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Sat, 04 Jul 2009 10:55:44 +0100, Vilya Harvey wrote:

> 2009/7/4 Andre Engels <andreengels [at] gmail>:
>> On Sat, Jul 4, 2009 at 9:33 AM, mclovin<hanooter [at] gmail> wrote:
>>> Currently I need to find the most common elements in thousands of
>>> arrays within one large array (arround 2 million instances with ~70k
>>> unique elements)
...
>> There's no better algorithm for the general case. No method of checking
>> the matrices using less than 2000000-x look-ups will ensure you that
>> there's not a new value with x occurences lurking somewhere.
>
> Try flattening the arrays into a single large array & sorting it. Then
> you can just iterate over the large array counting as you go; you only
> ever have to insert into the dict once for each value and there's no
> lookups in the dict.

You're suggesting to do a whole bunch of work copying 2,000,000 pointers
into a single array, then a whole bunch of more work sorting that second
array (which is O(N*log N) on average), and then finally iterate over the
second array. Sure, that last step will on average involve fewer than
O(N) steps, but to get to that point you've already done more work than
just iterating over the array-of-arrays in the first place.

Now, if you're really lucky, your strategy can be done in fast C code
instead of slow Python code, and you might see a speed-up for values of N
which aren't too big. But I wouldn't put money on it.

Another strategy might be to pre-count elements in each array, as you
build or modify them. This will marginally slow down each modification
you make to the array, but the payback will be that finding the frequency
of any element will be almost instantaneous.

--
Steven
--
http://mail.python.org/mailman/listinfo/python-list

Scott.Daniels at Acm

Jul 4, 2009, 7:19 AM

Post #7 of 27 (1192 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

Vilya Harvey wrote:
> 2009/7/4 Andre Engels <andreengels [at] gmail>:
>> On Sat, Jul 4, 2009 at 9:33 AM, mclovin<hanooter [at] gmail> wrote:
>>> Currently I need to find the most common elements in thousands of
>>> arrays within one large array (arround 2 million instances with ~70k
>>> unique elements)...
> Try flattening the arrays into a single large array & sorting it. Then
> you can just iterate over the large array counting as you go; you only
> ever have to insert into the dict once for each value and there's no
> lookups in the dict....

Actually the next step is to maintain a min-heap as you run down the
sorted array. Something like:

import numpy as np
import heapq

def frequency(arr):
'''Generate frequency-value pairs from a numpy array'''
clustered = arr.flatten() # copy (so can safely sort)
clustered.sort() # Bring identical values together
scanner = iter(clustered)
last = scanner.next()
count = 1
for el in scanner:
if el == last:
count += 1
else:
yield count, last
last = el
count = 1
yield count, last

def most_frequent(arr, N):
'''Return the top N (freq, val) elements in arr'''
counted = frequency(arr) # get an iterator for freq-val pairs
heap = []
# First, just fill up the array with the first N distinct
for i in range(N):
try:
heap.append(counted.next())
except StopIteration:
break # If we run out here, no need for a heap
else:
# more to go, switch to a min-heap, and replace the least
# element every time we find something better
heapq.heapify(heap)
for pair in counted:
if pair > heap[0]:
heapq.heapreplace(heap, pair)
return sorted(heap, reverse=True) # put most frequent first.

--Scott David Daniels
Scott.Daniels [at] Acm
--
http://mail.python.org/mailman/listinfo/python-list

steve at REMOVE-THIS-cybersource

Jul 4, 2009, 7:38 AM

Post #8 of 27 (1185 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Sat, 04 Jul 2009 13:42:06 +0000, Steven D'Aprano wrote:

> On Sat, 04 Jul 2009 10:55:44 +0100, Vilya Harvey wrote:
>
>> 2009/7/4 Andre Engels <andreengels [at] gmail>:
>>> On Sat, Jul 4, 2009 at 9:33 AM, mclovin<hanooter [at] gmail> wrote:
>>>> Currently I need to find the most common elements in thousands of
>>>> arrays within one large array (arround 2 million instances with ~70k
>>>> unique elements)
> ...
>>> There's no better algorithm for the general case. No method of
>>> checking the matrices using less than 2000000-x look-ups will ensure
>>> you that there's not a new value with x occurences lurking somewhere.
>>
>> Try flattening the arrays into a single large array & sorting it. Then
>> you can just iterate over the large array counting as you go; you only
>> ever have to insert into the dict once for each value and there's no
>> lookups in the dict.
>
> You're suggesting to do a whole bunch of work copying 2,000,000 pointers
> into a single array, then a whole bunch of more work sorting that second
> array (which is O(N*log N) on average), and then finally iterate over
> the second array. Sure, that last step will on average involve fewer
> than O(N) steps,

Er what?

Ignore that last comment -- I don't know what I was thinking. You still
have to iterate over all N elements, sorted or not.

> but to get to that point you've already done more work
> than just iterating over the array-of-arrays in the first place.

What it does buy you though, as you pointed out, is reducing the number
of explicit dict lookups and writes. However, dict lookups and writes are
very fast, fast enough that they're used throughout Python. A line like:

count += 1

actually is a dict lookup and write.

--
Steven
--
http://mail.python.org/mailman/listinfo/python-list

hanooter at gmail

Jul 4, 2009, 9:22 AM

Post #9 of 27 (1191 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

OK then. I will try some of the strategies here but I guess things
arent looking too good. I need to run this over a dataset that someone
pickled. I need to run this 480,000 times so you can see my
frustration. So it doesn't need to be "real time" but it would be nice
it was done sorting this month.

Is there a "bet guess" strategy where it is not 100% accurate but much
faster?

On Jul 4, 7:38�am, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.au> wrote:
> On Sat, 04 Jul 2009 13:42:06 +0000, Steven D'Aprano wrote:
> > On Sat, 04 Jul 2009 10:55:44 +0100, Vilya Harvey wrote:
>
> >> 2009/7/4 Andre Engels <andreeng...@gmail.com>:
> >>> On Sat, Jul 4, 2009 at 9:33 AM, mclovin<hanoo...@gmail.com> wrote:
> >>>> Currently I need to find the most common elements in thousands of
> >>>> arrays within one large array (arround 2 million instances with ~70k
> >>>> unique elements)
> > ...
> >>> There's no better algorithm for the general case. No method of
> >>> checking the matrices using less than 2000000-x look-ups will ensure
> >>> you that there's not a new value with x occurences lurking somewhere.
>
> >> Try flattening the arrays into a single large array & sorting it. Then
> >> you can just iterate over the large array counting as you go; you only
> >> ever have to insert into the dict once for each value and there's no
> >> lookups in the dict.
>
> > You're suggesting to do a whole bunch of work copying 2,000,000 pointers
> > into a single array, then a whole bunch of more work sorting that second
> > array (which is O(N*log N) on average), and then finally iterate over
> > the second array. Sure, that last step will on average involve fewer
> > than O(N) steps,
>
> Er what?
>
> Ignore that last comment -- I don't know what I was thinking. You still
> have to iterate over all N elements, sorted or not.
>
> > but to get to that point you've already done more work
> > than just iterating over the array-of-arrays in the first place.
>
> What it does buy you though, as you pointed out, is reducing the number
> of explicit dict lookups and writes. However, dict lookups and writes are
> very fast, fast enough that they're used throughout Python. A line like:
>
> count += 1
>
> actually is a dict lookup and write.
>
> --
> Steven

--
http://mail.python.org/mailman/listinfo/python-list

vilya.harvey at gmail

Jul 4, 2009, 10:59 AM

Post #10 of 27 (1187 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

2009/7/4 Steven D'Aprano <steve [at] remove-this-cybersource>:
> On Sat, 04 Jul 2009 13:42:06 +0000, Steven D'Aprano wrote:
>
>> On Sat, 04 Jul 2009 10:55:44 +0100, Vilya Harvey wrote:
>>
>>> 2009/7/4 Andre Engels <andreengels [at] gmail>:
>>>> On Sat, Jul 4, 2009 at 9:33 AM, mclovin<hanooter [at] gmail> wrote:
>>>>> Currently I need to find the most common elements in thousands of
>>>>> arrays within one large array (arround 2 million instances with ~70k
>>>>> unique elements)
>> ...
>>>> There's no better algorithm for the general case. No method of
>>>> checking the matrices using less than 2000000-x look-ups will ensure
>>>> you that there's not a new value with x occurences lurking somewhere.
>>>
>>> Try flattening the arrays into a single large array & sorting it. Then
>>> you can just iterate over the large array counting as you go; you only
>>> ever have to insert into the dict once for each value and there's no
>>> lookups in the dict.
>>
>> You're suggesting to do a whole bunch of work copying 2,000,000 pointers
>> into a single array, then a whole bunch of more work sorting that second
>> array (which is O(N*log N) on average), and then finally iterate over
>> the second array. Sure, that last step will on average involve fewer
>> than O(N) steps,
>
> Er what?
>
> Ignore that last comment -- I don't know what I was thinking. You still
> have to iterate over all N elements, sorted or not.
>
>> but to get to that point you've already done more work
>> than just iterating over the array-of-arrays in the first place.
>
> What it does buy you though, as you pointed out, is reducing the number
> of explicit dict lookups and writes. However, dict lookups and writes are
> very fast, fast enough that they're used throughout Python. A line like:
>
> count += 1
>
> actually is a dict lookup and write.

I did some tests, just to be sure, and you're absolutely right: just
creating the flattened list took several hundred (!) times as long as
iterating through all the lists in place. Live and learn...

Vil.
--
http://mail.python.org/mailman/listinfo/python-list

lie.1296 at gmail

Jul 4, 2009, 11:36 AM

Post #11 of 27 (1183 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

Scott.Daniels at Acm

Jul 4, 2009, 12:51 PM

Post #12 of 27 (1186 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

mclovin wrote:
> OK then. I will try some of the strategies here but I guess things
> arent looking too good. I need to run this over a dataset that someone
> pickled. I need to run this 480,000 times so you can see my
> frustration. So it doesn't need to be "real time" but it would be nice
> it was done sorting this month.
>
> Is there a "bet guess" strategy where it is not 100% accurate but much
> faster?

Well, I timed a run of a version of mine, and the scan is approx 5X
longer than the copy-and-sort. Time arr_of_arr.flatten().sort() to
see how quickly the copy and sort happens.So you could try a variant
exploiting the following property:
If you know the minimum length of a run that will be in the top 25,
then the value for each of the most-frequent run entries must show up at
positions n * stride and (n + 1) * stride (for some n). That should
drastically reduce the scan cost, as long as stride is reasonably large.

For my uniformly distributed 0..1024 values in 5M x 5M array,
About 2.5 sec to flatten and sort.
About 15 sec to run one of my heapish thingies.
the least frequency encountered: 24716
so, with stride at

sum(flattened[:-stride:stride] == flattened[stride::stride]) == 1000
So there are only 1000 points to investigate.
With any distribution other than uniform, that should go _way_ down.
So just pull out those points, use bisect to get their frequencies, and
feed those results into the heap accumulation.

--Scott David Daniels
--
http://mail.python.org/mailman/listinfo/python-list

hanooter at gmail

Jul 4, 2009, 3:06 PM

Post #13 of 27 (1173 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Jul 4, 12:51�pm, Scott David Daniels <Scott.Dani...@Acm.Org> wrote:
> mclovin wrote:
> > OK then. I will try some of the strategies here but I guess things
> > arent looking too good. I need to run this over a dataset that someone
> > pickled. I need to run this 480,000 times so you can see my
> > frustration. So it doesn't need to be "real time" but it would be nice
> > it was done sorting this month.
>
> > Is there a "bet guess" strategy where it is not 100% accurate but much
> > faster?
>
> Well, I timed a run of a version of mine, and the scan is approx 5X
> longer than the copy-and-sort. �Time arr_of_arr.flatten().sort() to
> see how quickly the copy and sort happens.So you could try a variant
> exploiting the following property:
> � � �If you know the minimum length of a run that will be in the top 25,
> then the value for each of the most-frequent run entries must show up at
> positions n * stride and (n + 1) * stride (for some n). �That should
> drastically reduce the scan cost, as long as stride is reasonably large.
>
> For my uniformly distributed 0..1024 values in 5M x 5M array,
> About 2.5 sec to flatten and sort.
> About 15 sec to run one of my heapish thingies.
> the least frequency encountered: 24716
> so, with stride at
>
> sum(flattened[:-stride:stride] == flattened[stride::stride]) == 1000
> So there are only 1000 points to investigate.
> With any distribution other than uniform, that should go _way_ down.
> So just pull out those points, use bisect to get their frequencies, and
> feed those results into the heap accumulation.
>
> --Scott David Daniels

I dont quite understand what you are saying but I know this: the times
the most common element appears varies greatly. Sometimes it appears
over 1000 times, and some times it appears less than 50. It all
depends on the density of the arrays I am analyzing.

like I said I need to do this 480,000 times so to get this done
realistically I need to analyse about 5 a second. It appears that the
average matrix size contains about 15 million elements.

I threaded my program using your code and I did about 1,000 in an hour
so it is still much too slow.

When I selected 1 million random elements to count, 8 out of the top
10 of those were in the top 25 of the precise way and 18 of the 25
were in the top 25 of the precise way. so I suppose that could be an
option.
--
http://mail.python.org/mailman/listinfo/python-list

python at mrabarnett

Jul 4, 2009, 3:29 PM

Post #14 of 27 (1172 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

mclovin wrote:
[snip]
> like I said I need to do this 480,000 times so to get this done
> realistically I need to analyse about 5 a second. It appears that the
> average matrix size contains about 15 million elements.
>
> I threaded my program using your code and I did about 1,000 in an hour
> so it is still much too slow.
>
> When I selected 1 million random elements to count, 8 out of the top
> 10 of those were in the top 25 of the precise way and 18 of the 25
> were in the top 25 of the precise way. so I suppose that could be an
> option.

The values are integers, aren't they? What is the range of values?
--
http://mail.python.org/mailman/listinfo/python-list

hanooter at gmail

Jul 4, 2009, 3:33 PM

Post #15 of 27 (1177 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Jul 4, 3:29�pm, MRAB <pyt...@mrabarnett.plus.com> wrote:
> mclovin wrote:
>
> [snip]
>
> > like I said I need to do this 480,000 times so to get this done
> > realistically I need to analyse about 5 a second. It appears that the
> > average matrix size contains about 15 million elements.
>
> > I threaded my program using your code and I did about 1,000 in an hour
> > so it is still much too slow.
>
> > When I selected 1 million random elements to count, 8 out of the top
> > 10 of those were in the top 25 of the precise way and 18 of the 25
> > were in the top 25 of the precise way. so I suppose that could be an
> > option.
>
> The values are integers, aren't they? What is the range of values?

There are appox 550k unique values with a range of 0-2million with
gaps.
--
http://mail.python.org/mailman/listinfo/python-list

Scott.Daniels at Acm

Jul 4, 2009, 3:50 PM

Post #16 of 27 (1169 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

mclovin wrote:
> On Jul 4, 12:51 pm, Scott David Daniels <Scott.Dani...@Acm.Org> wrote:
>> mclovin wrote:
>>> OK then. I will try some of the strategies here but I guess things
>>> arent looking too good. I need to run this over a dataset that someone
>>> pickled. I need to run this 480,000 times so you can see my
>>> frustration. So it doesn't need to be "real time" but it would be nice
>>> it was done sorting this month.
>>> Is there a "bet guess" strategy where it is not 100% accurate but much
>>> faster?
>>
>> Well, I timed a run of a version of mine, and the scan is approx 5X
>> longer than the copy-and-sort. Time arr_of_arr.flatten().sort() to
>> see how quickly the copy and sort happens.So you could try a variant
>> exploiting the following property:
>> If you know the minimum length of a run that will be in the top 25,
>> then the value for each of the most-frequent run entries must show up at
>> positions n * stride and (n + 1) * stride (for some n). That should
>> drastically reduce the scan cost, as long as stride is reasonably large....
>>
>> sum(flattened[:-stride:stride] == flattened[stride::stride]) == 1000
>> So there are only 1000 points to investigate.
>> With any distribution other than uniform, that should go _way_ down.
>> So just pull out those points, use bisect to get their frequencies, and
>> feed those results into the heap accumulation.
>>
>> --Scott David Daniels
>
> I dont quite understand what you are saying but I know this: the times
> the most common element appears varies greatly. Sometimes it appears
> over 1000 times, and some times it appears less than 50. It all
> depends on the density of the arrays I am analyzing.

Here's a heuristic replacement for my previous frequency code:
I've tried to mark where you could fudge numbers if the run time
is at all close.

def frequency(arr_of_arr, N, stride=100)
'''produce (freq, value) pairs for data in arr_of_arr.

Tries to produce > N pairs. stride is a guess at half
the length of the shortest run in the top N runs.
'''
# if the next two lines are too slow, this whole approach is toast
data = arr_of_arr.flatten() # big allocation
data.sort() # a couple of seconds for 25 million ints

# stride is a length forcing examination of a run.
sampled = data[::stride]
# Note this is a view into data, and is still sorted.
# We know that any run of length 2 * stride - 1 in data _must_ have
# consecutive entries in sampled. Compare them "in parallel"
matches = sampled[:-1] == sampled[1:]
# matches is True or False for stride-separated values from sampled
candidates = sum(matches) # count identified matches

# while candidates is huge, keep trying with a larger stride
while candidates > N *10: # 10 -- heuristic
stride *= 2 # # heuristic increase
sampled = data[::stride]
matches = sampled[:-1] == sampled[1:]
candidates = sum(matches)

# if we got too few, move stride down:
while candidates < N * 3: # heuristic slop for long runs
stride //= 2 # heuristic decrease
sampled = data[::stride]
matches = sampled[:-1] == sampled[1:]
candidates = sum(matches)

# Here we have a "nice" list of candidates that is likely
# to include every run we actually want. sampled[matches] is
# the sorted list of candidate values. It may have duplicates
former = None
past = 0
# In the loop here we only use sampled to the pick values we
# then go find in data. We avoid checking for same value twice
for value in sampled[matches]:
if value == former:
continue # A long run: multiple matches in sampled
former = value # Make sure we only try this one once
# find the beginning of the run
start = bisect.bisect_left(data, value, past)
# find the end of the run (we know it is at least stride long)
past = bisect.bisect_right(data, value, start + stride)
yield past - start, value # produce frequency, value data

--Scott David Daniels
Scott.Daniels [at] Acm
--
http://mail.python.org/mailman/listinfo/python-list

python at mrabarnett

Jul 4, 2009, 4:05 PM

Post #17 of 27 (1170 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

mclovin wrote:
> On Jul 4, 3:29 pm, MRAB <pyt...@mrabarnett.plus.com> wrote:
>> mclovin wrote:
>>
>> [snip]
>>
>>> like I said I need to do this 480,000 times so to get this done
>>> realistically I need to analyse about 5 a second. It appears that the
>>> average matrix size contains about 15 million elements.
>>> I threaded my program using your code and I did about 1,000 in an hour
>>> so it is still much too slow.
>>> When I selected 1 million random elements to count, 8 out of the top
>>> 10 of those were in the top 25 of the precise way and 18 of the 25
>>> were in the top 25 of the precise way. so I suppose that could be an
>>> option.
>> The values are integers, aren't they? What is the range of values?
>
> There are appox 550k unique values with a range of 0-2million with
> gaps.

I've done a little experimentation with lists (no numpy involved) and
found that I got a x2 speed increase if I did the counting using a list,
something like this:

counts = [0] * 2000000
for x in values:
counts[x] += 1
counts = dict(e for e in enumerate(values) if e[1] != 0)
--
http://mail.python.org/mailman/listinfo/python-list

emile at fenx

Jul 4, 2009, 6:00 PM

Post #18 of 27 (1166 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On 7/4/2009 12:33 AM mclovin said...
> Currently I need to find the most common elements in thousands of
> arrays within one large array (arround 2 million instances with ~70k
> unique elements)
>
> so I set up a dictionary to handle the counting so when I am
> iterating I

** up the count on the corrosponding dictionary element **

Right at this point, instead of or in addition to counting, why not save
the large array index in a list? Then when you've identified the 25
most common elements you'll already have a list of pointer to the
instances to work from.

Emile

--
http://mail.python.org/mailman/listinfo/python-list

steve at REMOVE-THIS-cybersource

Jul 4, 2009, 6:31 PM

Post #19 of 27 (1140 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Sat, 04 Jul 2009 15:06:29 -0700, mclovin wrote:

> like I said I need to do this 480,000 times so to get this done
> realistically I need to analyse about 5 a second. It appears that the
> average matrix size contains about 15 million elements.

Have you considered recording the element counts as you construct the
arrays? This will marginally increase the time it takes to build the
array, but turn finding the most frequent elements into a very quick
operation.

--
Steven
--
http://mail.python.org/mailman/listinfo/python-list

steve at REMOVE-THIS-cybersource

Jul 4, 2009, 6:39 PM

Post #20 of 27 (1146 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Sat, 04 Jul 2009 07:19:48 -0700, Scott David Daniels wrote:

> Actually the next step is to maintain a min-heap as you run down the
> sorted array. Something like:

Not bad.

I did some tests on it, using the following sample data:

arr = np.array([xrange(i, i+7000) for i in xrange(143)] +
[[750]*7000] + [xrange(3*i, 3*i+7000) for i in xrange(142)])

and compared your code against the following simple function:

def count(arr, N):
D = {}
for v in arr:
for x in v:
D[x] = D.get(x, 0) + 1
freq = []
for el, f in D.iteritems():
freq.append((f, el))
return sorted(freq, reverse=True)[:N]

As a rough figure, your min-heap code is approximately twice as fast as
mine.

To the OP: I think you should start profiling your code and find out
exactly *where* it is slow and concentrate on that. I think that trying a
heuristic to estimate the most frequent elements by taking a random
sample is likely to be a mistake -- whatever you're trying to accomplish
with the frequency counts, the use of such a heuristic will mean that
you're only approximately accomplishing it.

--
Steven
--
http://mail.python.org/mailman/listinfo/python-list

Scott.Daniels at Acm

Jul 5, 2009, 5:30 PM

Post #21 of 27 (1092 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

Scott David Daniels wrote:
> ... Here's a heuristic replacement for my previous frequency code:
> I've tried to mark where you could fudge numbers if the run time
> is at all close.

Boy, I cannot let go. I did a bit of a test checking for cost to
calculated number of discovered samples, and found after:
import timeit
import numpy
original = numpy.random.random(0, 100, (1000, 1000)).astype(int)
data = original.flatten()
data.sort()
part = data[::100]
t = timeit.Timer('sum(part[:-1]==part[1:])',
'from __main__ import part')
v = timeit.Timer('len(part[part[:-1]==part[1:]])',
'from __main__ import part')

I got:
>>> t.repeat(3, 10)
[0.58319842326318394, 0.57617574300638807, 0.57831819407238072]
>>> v.repeat(3, 1000)
[0.93933027801040225, 0.93704535073584339, 0.94096260837613954]

So, len(part[mask]) is almost 50X faster! I checked:
>>> sum(part[:-1]==part[1:])
9393
>>> len(part[part[:-1]==part[1:]])
9393

That's an awful lot of matches, so I with high selectivity:
data = original.flatten() # no sorting, so runs missing
part = data[::100]

>>> t.repeat(3, 10)
[0.58641335700485797, 0.58458854407490435, 0.58872594142576418]
>>> v.repeat(3, 1000)
[0.27352554584422251, 0.27375686015921019, 0.27433291102624935]

about 200X faster

>>> len(part[part[:-1]==part[1:]])
39
>>> sum(part[:-1]==part[1:])
39

So my new version of this (compressed) code:
> ...
> sampled = data[::stride]
> matches = sampled[:-1] == sampled[1:]
> candidates = sum(matches) # count identified matches
> while candidates > N * 10: # 10 -- heuristic
> stride *= 2 # # heuristic increase
> sampled = data[::stride]
> matches = sampled[:-1] == sampled[1:]
> candidates = sum(matches)
> while candidates < N * 3: # heuristic slop for long runs
> stride //= 2 # heuristic decrease
> sampled = data[::stride]
> matches = sampled[:-1] == sampled[1:]
> candidates = sum(matches)
> former = None
> past = 0
> for value in sampled[matches]:
> ...
is:
...
sampled = data[::stride]
candidates = sampled[sampled[:-1] == sampled[1:]]
while len(candidates) > N * 10: # 10 -- heuristic
stride *= 2 # # heuristic increase
sampled = data[::stride]
candidates = sampled[sampled[:-1] == sampled[1:]]
while len(candidates) < N * 3: # heuristic slop for long runs
stride //= 2 # heuristic decrease
sampled = data[::stride]
candidates = sampled[sampled[:-1] == sampled[1:]]
former = None
past = 0
for value in candidates:
...
This change is important, for we try several strides before
settling on a choice, meaning the optimization can be valuable.
This also means we could be pickier at choosing strides (try
more values), since checking is cheaper than before.

Summary: when dealing with numpy, (or any bulk <-> individual values
transitions), try several ways that you think are equivalent and
_measure_. In the OODB work I did we called this "impedance mismatch,"
and it is likely some boundary transitions are _much_ faster than
others. The sum case is one of them; I am getting numpy booleans
back, rather than numpy booleans, so conversions aren't going fastpath.

--Scott David Daniels
Scott.Daniels [at] Acm
--
http://mail.python.org/mailman/listinfo/python-list

steve at REMOVE-THIS-cybersource

Jul 5, 2009, 8:28 PM

Post #22 of 27 (1081 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

On Sun, 05 Jul 2009 17:30:58 -0700, Scott David Daniels wrote:

> Summary: when dealing with numpy, (or any bulk <-> individual values
> transitions), try several ways that you think are equivalent and
> _measure_.

This advice is *much* more general than numpy -- it applies to any
optimization exercise. People's intuitions about what's fast and what's
slow are often very wrong.

--
Steven
--
http://mail.python.org/mailman/listinfo/python-list

__peter__ at web

Jul 5, 2009, 11:33 PM

Post #23 of 27 (1078 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

Scott David Daniels wrote:

> Scott David Daniels wrote:

> t = timeit.Timer('sum(part[:-1]==part[1:])',
> 'from __main__ import part')

What happens if you calculate the sum in numpy? Try

t = timeit.Timer('(part[:-1]==part[1:]).sum()',
'from __main__ import part')

Peter

--
http://mail.python.org/mailman/listinfo/python-list

Scott.Daniels at Acm

Jul 6, 2009, 6:59 AM

Post #24 of 27 (1060 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

Peter Otten wrote:
> Scott David Daniels wrote:
>
>> Scott David Daniels wrote:
>
>> t = timeit.Timer('sum(part[:-1]==part[1:])',
>> 'from __main__ import part')
>
> What happens if you calculate the sum in numpy? Try
>
> t = timeit.Timer('(part[:-1]==part[1:]).sum()',
> 'from __main__ import part')

Good idea, I hadn't thought of adding numpy bools.
(part[:-1]==part[1:]).sum()
is only a slight improvement over
len(part[part[:-1]==part[1:]])
when there are few elements, but it is almost twice
as fast when there are a lot (reflecting the work
of allocating and copying).

>>> import numpy
>>> import timeit
>>> original = numpy.random.normal(0, 100, (1000, 1000)).astype(int)
>>> data = original.flatten()
>>> data.sort()
>>> t = timeit.Timer('sum(part[:-1]==part[1:])',
'from __main__ import part')
>>> u = timeit.Timer('len(part[part[:-1]==part[1:]])',
'from __main__ import part')
>>> v = timeit.Timer('(part[:-1]==part[1:]).sum()',
'from __main__ import part')

>>> part = data[::100]
>>> (part[:-1]==part[1:]).sum()
9390
>>> t.repeat(3, 10)
[0.56368281443587875, 0.55615057220961717, 0.55465764503594528]
>>> u.repeat(3, 1000)
[0.89576580263690175, 0.89276374511291579, 0.8937328626963108]
>>> v.repeat(3, 1000)
[0.24798598704592223, 0.24715431709898894, 0.24498979618920202]
>>>
>>> part = original.flatten()[::100]
>>> (part[:-1]==part[1:]).sum()
27
>>> t.repeat(3, 10)
[0.57576898739921489, 0.56410158274297828, 0.56988248506445416]
>>> u.repeat(3, 1000)
[0.27312186325366383, 0.27315007913011868, 0.27214492344683094]
>>> v.repeat(3, 1000)
[0.28410342655297427, 0.28374053126867693, 0.28318990262732768]
>>>

Net result: go back to former definition of candidates (a number,
not the actual entries), but calculate that number as matches.sum(),
not len(part[matches]).

Now the latest version of this (compressed) code:
> ...
> sampled = data[::stride]
> matches = sampled[:-1] == sampled[1:]
> candidates = sum(matches) # count identified matches
> while candidates > N * 10: # 10 -- heuristic
> stride *= 2 # # heuristic increase
> sampled = data[::stride]
> matches = sampled[:-1] == sampled[1:]
> candidates = sum(matches)
> while candidates < N * 3: # heuristic slop for long runs
> stride //= 2 # heuristic decrease
> sampled = data[::stride]
> matches = sampled[:-1] == sampled[1:]
> candidates = sum(matches)
> former = None
> past = 0
> for value in sampled[matches]:
> ...
is:
...
sampled = data[::stride]
matches = sampled[:-1] == sampled[1:]
candidates = matches.sum() # count identified matches
while candidates > N * 10: # 10 -- heuristic
stride *= 2 # # heuristic increase
sampled = data[::stride]
matches = sampled[:-1] == sampled[1:]
candidates = matches.sum()
while candidates < N * 3: # heuristic slop for long runs
stride //= 2 # heuristic decrease
sampled = data[::stride]
matches = sampled[:-1] == sampled[1:]
candidates = matches.sum()
former = None
past = 0
for value in sampled[matches]:
...

Now I think I can let this problem go, esp. since it was
mclovin's problem in the first place.

--Scott David Daniels
Scott.Daniels [at] Acm
--
http://mail.python.org/mailman/listinfo/python-list

andrew.henshaw at gtri

Jul 7, 2009, 2:48 PM

Post #25 of 27 (1026 views)
Permalink

Re: finding most common elements between thousands of multiple arrays. [In reply to]

"mclovin" <hanooter [at] gmail> wrote in message
news:c5332c9b-2348-4194-bfa0-d70c7710765d [at] x3g2000yqa
> Currently I need to find the most common elements in thousands of
> arrays within one large array (arround 2 million instances with ~70k
> unique elements)
>
> so I set up a dictionary to handle the counting so when I am
> iterating I up the count on the corrosponding dictionary element. I
> then iterate through the dictionary and find the 25 most common
> elements.
>
> the elements are initially held in a array within an array. so I am am
> just trying to find the most common elements between all the arrays
> contained in one large array.
> my current code looks something like this:
> d = {}
> for arr in my_array:
> -----for i in arr:
> #elements are numpy integers and thus are not accepted as dictionary
> keys
> -----------d[int(i)]=d.get(int(i),0)+1
>
> then I filter things down. but with my algorithm that only takes about
> 1 sec so I dont need to show it here since that isnt the problem.
>
>
> But there has to be something better. I have to do this many many
> times and it seems silly to iterate through 2 million things just to
> get 25. The element IDs are integers and are currently being held in
> numpy arrays in a larger array. this ID is what makes up the key to
> the dictionary.
>
> It currently takes about 5 seconds to accomplish this with my current
> algorithm.
>
> So does anyone know the best solution or algorithm? I think the trick
> lies in matrix intersections but I do not know.

Would the following work for you, or am I missing something? For a 5Kx5K
array, this takes about a tenth of a second on my machine. This code
doesn't deal with the sub-array issue.

#####################
import numpy
import time

LOWER = 0
UPPER = 1024
SIZE = 5000
NUM_BEST = 4

# sample data
data = numpy.random.randint(LOWER, UPPER, (SIZE,SIZE)).astype(int)

time.clock()
count = numpy.bincount(data.flat)
best = sorted(zip(count, range(len(count))))[-NUM_BEST:]
print 'time=', time.clock()
print best

--
http://mail.python.org/mailman/listinfo/python-list

1 2

View All

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads