Hi,

does anyone know an algorithm for slowing the following problem faster then the solution proposed belove?

Problem :

Let D be a 2d array of integers.

[0] ->  1 4 6 8 9 ...
[1] ->  1 3 5 6 20 ...
[2] ->  2 3 4 5 6 ...
[3] ->  5 7 8 9 12 ...
[4] ->  3 5 8 11 13...
[5] ->  4 5 7 8 9 ...
[6] ->  1 4 5 7 8 ...
...
[download]

Integers range form 1 to 3000000. there are approximately 50000 ints in each [x] array. the number is not fixed and can be between 1 and 3000000. In each [x] array the numbers are ordered form smallest to largest (ALWAYS). Given n integers (example: 1,2,5,6) find top x integers in arrays [i_{1}]..[i_{n}] ([1],[2],[5],[6]) that are shared between them. in my case if x is 2 then my top 2 int values would be :

1. 5 -> is shared between all four arrays ([1],[2], [5], [6])
2. 4  -> is shared between 3 arrays ([2],[5], [6])
[download]

my solution (for the above small example): make a hash table using numbers in each [d] array, as keys and simply if a number has been encountered increment it. afterworlds just sort the array (biggest count to smallest) and pick first two.

for (1,2,5,6){
   foreach $ar (@{$D[$_]}){
      $hash{$ar}++;
   }
}

# sort %hash
#pick top two
[download]

however, such solution, if reaped a large number of times or if the numbers are large, tends not to be practical. Does anyone has any suggestion on how to pre-process the 2d array in order to speed the computation and save memory (hashes are expensive when it comes to memory)

thnx

PS

I was thinking of 2D-RMQ solution but i haven't looked into it yet hoping that there might be a slicker solution.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.