Is there a faster way of inserting N^2 items than using an N^2 Loop?

Question

You have a database where Many Foos have Many Bars, so:

Foo --< FooBar >-- Bar

You have 10 Foos and 10 Bars and need to associate every Foo with every Bar by inserting 100 records into FooBar

Is there a more efficient way to perform this other than the following N^2 Loop, or are we stuck with this?

def associate(foos, bars):
    for foo in foos:
        for bar in bars:
            # INSERT INTO foobar (foo_id, bar_id) VALUES (foo.id, bar.id)

Is it _[Someone has] 10 Foos and 10 Bars and needs to associate every Foo with every Bar using 100 records_, or would _[Someone has] 10 Foos and 10 Bars and needs to be able to query about every pair (Foo, Bar), and associate information with it_? — greybeard, Jun 07 '16 at 02:47
@greybeard the former is correct: associate 10 `Foos` with 10 `Bars` by inserting 100 records into `FooBar` — Matthew Moisen, Jun 07 '16 at 04:38

score 2 · Accepted Answer · edited May 23 '17 at 10:34

2

You need to insert n^2 elements. There is no way to do this faster than in n^2. The only thing I can suggest is to use batch insert instead of individual inserts.

edited May 23 '17 at 10:34

Community

1
1

answered Jun 06 '16 at 23:01

Salvador Dali

214,103
147
703
753

Yep, I'm actually adding the FooBars to a list and then bulk inserting them afterwards. – Matthew Moisen Jun 06 '16 at 23:02

score 2 · Answer 2 · answered Jun 06 '16 at 23:30

The only way you can get faster than O(n^2) is by not inserting n^2 elements. In your case, you could perhaps only store records where the two items are not related, if you expect to only have a few of these. In SQL, you could then form your queries to account for this, or in case of general usage, set up an updatable view to make such an inverted table act like normal.

Is there a faster way of inserting N^2 items than using an N^2 Loop?

2 Answers2