Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><strong>[Update] The algorithm presented here shouldn't improve time complexity compared to the OP's original algorithm.</strong> Both algorithms have the same asymptotic complexity, and iterating through sorted lists (as OP does) should generally perform better than using a hash table.</p> <p>You need to group the items by <code>product</code>, not by <code>country</code>, in order to be able to quickly fetch all countries belonging to a certain product.</p> <p>This would be the pseudocode:</p> <pre><code>inputList contains a list of pairs {country, product} // group by product prepare mapA (product) =&gt; (list_of_countries) for each {country, product} in inputList { if mapA does not contain (product) create a new empty (list_of_countries) and add it to mapA with (product) as key add this (country) to the (list_of_countries) } // now group by country_pair prepare mapB (country_pair) =&gt; (list_of_products) for each {product, list_of_countries} in mapA { for each pair {countryA, countryB} in list_of_countries { if mapB does not countain country_pair {countryA, countryB} create a new empty (list_of_products) and add it to mapB with country_pair {countryA, countryB} as key add this (product) to the (list_of_products) } } </code></pre> <p>If your input list is length N, and you have C distinct countries and P distinct products, then the running time of this algorithm should be <code>O(N)</code> for the first part and <code>O(P*C^2)</code> for the second part. Since your final list needs to have <strong>pairs of countries</strong> mapping to <strong>lists of products</strong>, I don't think you will be able to lose the <code>P*C^2</code> complexity in any case.</p> <p>I don't code in Java too much, so I added a C# example which I believe you'll be able to port pretty easily:</p> <pre><code>// mapA maps each product to a list of countries var mapA = new Dictionary&lt;string, List&lt;string&gt;&gt;(); foreach (var t in inputList) { List&lt;string&gt; countries = null; if (!mapA.TryGetValue(t.Product, out countries)) { countries = new List&lt;string&gt;(); mapA[t.Product] = countries; } countries.Add(t.Country); } // note (this is very important): // CountryPair tuple must have value-type comparison semantics, // i.e. you need to ensure that two CountryPairs are compared // by value to allow hashing (mapping) to work correctly, in O(1). // In C# you can also simply use a Tuple&lt;string,string&gt; to // represent a pair of countries (which implements this correctly), // but I used a custom class to emphasize the algorithm // mapB maps each CountryPair to a list of products var mapB = new Dictionary&lt;CountryPair, List&lt;string&gt;&gt;(); foreach (var kvp in mapA) { var product = kvp.Key; var countries = kvp.Value; for (int i = 0; i &lt; countries.Count; i++) { for (int j = i + 1; j &lt; countries.Count; j++) { var pair = CountryPair.Create(countries[i], countries[j]); List&lt;string&gt; productsForCountryPair = null; if (!mapB.TryGetValue(pair, out productsForCountryPair)) { productsForCountryPair = new List&lt;string&gt;(); mapB[pair] = productsForCountryPair; } productsForCountryPair.Add(product); }* } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POPairWise matching millions of records
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USGroo
    1. USGroo
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI had run this new implementation where I group by exports rather than Country. It's been running since Friday evening. My Question, is how does this new implementation reduce computational complexity. I find that the complexity is almost same. The only difference between the intersection between the lists. Correct me if I am wrong.
      singulars
      1. PO
      1. USprog_guy
    2. COThe most important part of this algorithm is to implement the `CountryPair` equality/hashing functionality properly. This means you will have to [override `equals`/`getHashCode`](http://stackoverflow.com/questions/27581/overriding-equals-and-hashcode-in-java) and ensure that your hash function does not provide too many collisions. You can also use any tuple class which implements equality this way (e.g. [javatuples](http://www.javatuples.org/)). If your hash function is written poorly, then you will lose `O(1)` lookup for the country pair map, and time will degrade.
      singulars
      1. PO
      1. USGroo
    3. CO@prog_guy: I have also edit my answer with some complexity analysis, so you can check if my numbers are correct.
      singulars
      1. PO
      1. USGroo
 

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