Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>EDIT: The "start from anywhere, extended range" version...</p> <p>This version has a signficantly extended range, and therefore returns an <code>IEnumerable&lt;long&gt;</code> instead of an <code>IEnumerable&lt;int&gt;</code> - multiply enough digits together and you exceed <code>int.MaxValue</code>. It also goes up to 10,000,000,000,000,000 - not quite the full range of <code>long</code>, but pretty big :) You can start anywhere you like, and it will carry on from there to its end.</p> <pre><code>class DigitProducts { private static readonly int[] Prefilled = CreateFirst10000(); private static int[] CreateFirst10000() { // Inefficient but simple, and only executed once. int[] values = new int[10000]; for (int i = 0; i &lt; 10000; i++) { int product = 1; foreach (var digit in i.ToString()) { product *= digit -'0'; } values[i] = product; } return values; } public static IEnumerable&lt;long&gt; GetProducts(long startingPoint) { if (startingPoint &gt;= 10000000000000000L || startingPoint &lt; 0) { throw new ArgumentOutOfRangeException(); } int a = (int) (startingPoint / 1000000000000L); int b = (int) ((startingPoint % 1000000000000L) / 100000000); int c = (int) ((startingPoint % 100000000) / 10000); int d = (int) (startingPoint % 10000); for (; a &lt; 10000; a++) { long aMultiplier = a == 0 ? 1 : Prefilled[a]; for (; b &lt; 10000; b++) { long bMultiplier = a == 0 &amp;&amp; b == 0 ? 1 : a != 0 &amp;&amp; b &lt; 1000 ? 0 : Prefilled[b]; for (; c &lt; 10000; c++) { long cMultiplier = a == 0 &amp;&amp; b == 0 &amp;&amp; c == 0 ? 1 : (a != 0 || b != 0) &amp;&amp; c &lt; 1000 ? 0 : Prefilled[c]; long abcMultiplier = aMultiplier * bMultiplier * cMultiplier; for (; d &lt; 10000; d++) { long dMultiplier = (a != 0 || b != 0 || c != 0) &amp;&amp; d &lt; 1000 ? 0 : Prefilled[d]; yield return abcMultiplier * dMultiplier; } d = 0; } c = 0; } b = 0; } } } </code></pre> <hr> <p>EDIT: Performance analysis</p> <p>I haven't looked at the performance in <em>detail</em>, but I believe at this point the bulk of the work is just simply iterating over a billion values. A simple <code>for</code> loop which just returns the value itself takes over 5 seconds on my laptop, and iterating over the digit products only takes a bit over 6 seconds, so I don't think there's much more room for optimization - if you want to go from the start. If you want to (efficiently) start from a different position, more tweaks are required.</p> <hr> <p>Okay, here's an attempt which uses an iterator block to yield the results, and precomputes the first thousand results to make things a bit quicker.</p> <p>I've tested it up to about 150 million, and it's correct so far. It only goes returns the first billion results - if you needed more than that, you could add another block at the end...</p> <pre><code>static IEnumerable&lt;int&gt; GetProductDigitsFast() { // First generate the first 1000 values to cache them. int[] productPerThousand = new int[1000]; // Up to 9 for (int x = 0; x &lt; 10; x++) { productPerThousand[x] = x; yield return x; } // Up to 99 for (int y = 1; y &lt; 10; y++) { for (int x = 0; x &lt; 10; x++) { productPerThousand[y * 10 + x] = x * y; yield return x * y; } } // Up to 999 for (int x = 1; x &lt; 10; x++) { for (int y = 0; y &lt; 10; y++) { for (int z = 0; z &lt; 10; z++) { int result = x * y * z; productPerThousand[x * 100 + y * 10 + z] = x * y * z; yield return result; } } } // Now use the cached values for the rest for (int x = 0; x &lt; 1000; x++) { int xMultiplier = x == 0 ? 1 : productPerThousand[x]; for (int y = 0; y &lt; 1000; y++) { // We've already yielded the first thousand if (x == 0 &amp;&amp; y == 0) { continue; } // If x is non-zero and y is less than 100, we've // definitely got a 0, so the result is 0. Otherwise, // we just use the productPerThousand. int yMultiplier = x == 0 || y &gt;= 100 ? productPerThousand[y] : 0; int xy = xMultiplier * yMultiplier; for (int z = 0; z &lt; 1000; z++) { if (z &lt; 100) { yield return 0; } else { yield return xy * productPerThousand[z]; } } } } } </code></pre> <p>I've tested this by comparing it with the results of an incredibly naive version:</p> <pre><code>static IEnumerable&lt;int&gt; GetProductDigitsSlow() { for (int i = 0; i &lt; 1000000000; i++) { int product = 1; foreach (var digit in i.ToString()) { product *= digit -'0'; } yield return product; } } </code></pre> <p>Hope this idea is of some use... I don't know how it compares to the others shown here in terms of performance.</p> <p>EDIT: Expanding this slightly, to use simple loops where we know the results will be 0, we end up with fewer conditions to worry about, but for some reason it's actually slightly slower. (This really surprised me.) This code is longer, but possibly a little easier to follow.</p> <pre><code>static IEnumerable&lt;int&gt; GetProductDigitsFast() { // First generate the first 1000 values to cache them. int[] productPerThousand = new int[1000]; // Up to 9 for (int x = 0; x &lt; 10; x++) { productPerThousand[x] = x; yield return x; } // Up to 99 for (int y = 1; y &lt; 10; y++) { for (int x = 0; x &lt; 10; x++) { productPerThousand[y * 10 + x] = x * y; yield return x * y; } } // Up to 999 for (int x = 1; x &lt; 10; x++) { for (int y = 0; y &lt; 10; y++) { for (int z = 0; z &lt; 10; z++) { int result = x * y * z; productPerThousand[x * 100 + y * 10 + z] = x * y * z; yield return result; } } } // Use the cached values up to 999,999 for (int x = 1; x &lt; 1000; x++) { int xMultiplier = productPerThousand[x]; for (int y = 0; y &lt; 100; y++) { yield return 0; } for (int y = 100; y &lt; 1000; y++) { yield return xMultiplier * y; } } // Now use the cached values for the rest for (int x = 1; x &lt; 1000; x++) { int xMultiplier = productPerThousand[x]; // Within each billion, the first 100,000 values will all have // a second digit of 0, so we can just yield 0. for (int y = 0; y &lt; 100 * 1000; y++) { yield return 0; } for (int y = 100; y &lt; 1000; y++) { int yMultiplier = productPerThousand[y]; int xy = xMultiplier * yMultiplier; // Within each thousand, the first 100 values will all have // an anti-penulimate digit of 0, so we can just yield 0. for (int z = 0; z &lt; 100; z++) { yield return 0; } for (int z = 100; z &lt; 1000; z++) { yield return xy * productPerThousand[z]; } } } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POHow to calculate the digit products of the consecutive numbers efficiently?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJon Skeet
    1. USJon Skeet
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow to calculate the digit products of the consecutive numbers efficiently?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis answer is easier to understand than some of the others. I think the iterator block is relatively slow, but use array(s) as the cache is a good idea. The insteresting thing is how the cache is used, for example, for a 10 digits number `1234567891`, we can seperate it to `1,234,567,891` or `1,23,456,789,1`. When the numbers are more larger, there are various strategies of the seperation of digits and the cache size. I've once thought that bisection the length of digits would be a good way for divide and conquer, but I don't know whether it's the fact.
      singulars
      1. PO
      1. USKen Kin
    2. CO@KenKin: I don't think the iterator block makes much difference. I've just written an alternative version which accepts an `Action<int>`, and both versions take about 6 seconds on my laptop to work through all 1 billion that it produces.
      singulars
      1. PO
      1. USJon Skeet
    3. COYou are right, no much difference. Perhaps the subtle difference occured in my test was caused by the instruction-generation or optimization. But the efficiency between the iterator pattern and tail recursion is tricky.
      singulars
      1. PO
      1. USKen Kin
 

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