Databases
StackOverflow2013
Postsdbo
POFinding n-th biggest product in a large matrix of numbers, fast
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFinding n-th biggest product in a large matrix of numbers, fast
    primarykey
    data
    text
    <p>I'm working on a sorting/ranking algorithm that works with quite large number of items and I need to implement the following algorithm in an efficient way to make it work:</p> <hr> <p>There are two lists of numbers. They are equally long, about 100-500 thousand items. From this I need to find the n-th biggest product between these lists, ie. if you create a matrix where on top you have one list, on the side you have the other one and each cell is the product of the number above and the number on the side.</p> <p>Example: The lists are <code>A=[1, 3, 4]</code> and <code>B=[2, 2, 5]</code>. Then the products are <code>[2, 2, 5, 6, 6, 15, 8, 8, 20]</code>. If I wanted the 3rd biggest from that it would be 8.</p> <p>The naive solution would be to simply generate those numbers, sort them and then select the n-th biggest. But that is <code>O(m^2 * log m^2)</code> where m is the number of elements in the small lists, and that is just not fast enough.</p> <p>I think what I need is to first sort the two small lists. That is <code>O(m * log m)</code>. Then I know for sure that the biggest one A[0]*B[0]. Second biggest one is either A[0]*B[1] or A[1]*B[0], ...</p> <p>I feel like this could be done in <code>O(f(n))</code> steps, independent of the size of the matrix. But I can't figure out an efficient way to do this part.</p> <hr> <p>Edit: There was an answer that got deleted, which suggested to remember position in the two sorted sets and then look at A[a]*B[b+1] and A[a+1]*B[b], returning the bigger one and incrementing a/b. I was going to post this comment before it got deleted:</p> <blockquote> <p>This won't work. Imagine two lists A=B=[3,2,1]. This will give you matrix like [9,6,3 ; 6,4,2 ; 3,2,1]. So you start at (0,0)=9, go to (0,1)=6 and then the choice is (0,2)=3 or (1,1)=4. However, this will miss the (1,0)=6 which is bigger then both. So you can't just look to the two neighbors but you have to backtrack.</p> </blockquote>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USTimmy
    1. USTimmy
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFinding n-th biggest product in a large matrix of numbers, fast
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFinding n-th biggest product in a large matrix of numbers, fast
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFinding n-th biggest product in a large matrix of numbers, fast
      1. This table or related slice is empty.
      1. VTUpMod
    1. COn is bounded to the range (0..m^2), so I don't think you can claim that any O(f(n)) is independent of the size of the matrix.
      singulars
      1. POFinding n-th biggest product in a large matrix of numbers, fast
      1. USmbeckish
    2. COThe matrix generated is known as the outer product between the two vectors.
      singulars
      1. POFinding n-th biggest product in a large matrix of numbers, fast
      1. UStskuzzy
    3. COWhat is the range of your list values? If in practice the range is a lot smaller than the size of your lists, then an algorithm that is a function of the range size might work out better than an algorithm that is a function of the list size.
      singulars
      1. POFinding n-th biggest product in a large matrix of numbers, fast
      1. USmbeckish
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload