Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Using <code>GHC 7.0.3</code>, <code>gcc 4.4.6</code>, <code>Linux 2.6.29</code> on an x86_64 Core2 Duo (2.5GHz) machine, compiling using <code>ghc -O2 -fllvm -fforce-recomp</code> for Haskell and <code>gcc -O3 -lm</code> for C.</p> <ul> <li>Your C routine runs in 8.4 seconds (faster than your run probably because of <code>-O3</code>)</li> <li>The Haskell solution runs in 36 seconds (due to the <code>-O2</code> flag)</li> <li>Your <code>factorCount'</code> code isn't explicitly typed and defaulting to <code>Integer</code> (thanks to Daniel for correcting my misdiagnosis here!). Giving an explicit type signature (which is standard practice anyway) using <code>Int</code> and the time changes to <strong>11.1 seconds</strong></li> <li>in <code>factorCount'</code> you have needlessly called <code>fromIntegral</code>. A fix results in no change though (the compiler is smart, lucky for you).</li> <li>You used <code>mod</code> where <code>rem</code> is faster and sufficient. This changes the time to <strong>8.5 seconds</strong>.</li> <li><code>factorCount'</code> is constantly applying two extra arguments that never change (<code>number</code>, <code>sqrt</code>). A worker/wrapper transformation gives us:</li> </ul> <pre class="lang-hs prettyprint-override"><code> $ time ./so 842161320 real 0m7.954s user 0m7.944s sys 0m0.004s </code></pre> <p>That's right, <strong>7.95 seconds</strong>. Consistently <strong>half a second faster than the C solution</strong>. Without the <code>-fllvm</code> flag I'm still getting <code>8.182 seconds</code>, so the NCG backend is doing well in this case too.</p> <p>Conclusion: Haskell is awesome.</p> <p><strong>Resulting Code</strong></p> <pre class="lang-hs prettyprint-override"><code>factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare) where square = sqrt $ fromIntegral number isquare = floor square factorCount' :: Int -&gt; Int -&gt; Int -&gt; Int -&gt; Int factorCount' number sqrt candidate0 count0 = go candidate0 count0 where go candidate count | candidate &gt; sqrt = count | number `rem` candidate == 0 = go (candidate + 1) (count + 2) | otherwise = go (candidate + 1) count nextTriangle index triangle | factorCount triangle &gt; 1000 = triangle | otherwise = nextTriangle (index + 1) (triangle + index + 1) main = print $ nextTriangle 1 1 </code></pre> <p>EDIT: So now that we've explored that, lets address the questions</p> <blockquote> <p>Question 1: Do erlang, python and haskell lose speed due to using arbitrary length integers or don't they as long as the values are less than MAXINT?</p> </blockquote> <p>In Haskell, using <code>Integer</code> is slower than <code>Int</code> but how much slower depends on the computations performed. Luckily (for 64 bit machines) <code>Int</code> is sufficient. For portability sake you should probably rewrite my code to use <code>Int64</code> or <code>Word64</code> (C isn't the only language with a <code>long</code>).</p> <blockquote> <p>Question 2: Why is haskell so slow? Is there a compiler flag that turns off the brakes or is it my implementation? (The latter is quite probable as haskell is a book with seven seals to me.)</p> <p>Question 3: Can you offer me some hints how to optimize these implementations without changing the way I determine the factors? Optimization in any way: nicer, faster, more "native" to the language.</p> </blockquote> <p>That was what I answered above. The answer was </p> <ul> <li>0) Use optimization via <code>-O2</code> </li> <li>1) Use fast (notably: unbox-able) types when possible </li> <li>2) <code>rem</code> not <code>mod</code> (a frequently forgotten optimization) and </li> <li>3) worker/wrapper transformation (perhaps the most common optimization).</li> </ul> <blockquote> <p>Question 4: Do my functional implementations permit LCO and hence avoid adding unnecessary frames onto the call stack?</p> </blockquote> <p>Yes, that wasn't the issue. Good work and glad you considered this.</p>
    singulars
    1. This table or related slice is empty.
    1. POSpeed comparison with Project Euler: C vs Python vs Erlang vs Haskell
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCraig P. Motlin
    1. USThomas M. DuBuisson
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POSpeed comparison with Project Euler: C vs Python vs Erlang vs Haskell
      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. COWhy is there such a difference in speed between `rem` and `mod`?
      singulars
      1. PO
      1. USKarl Knechtel
    2. CO@Karl Because `rem` is actually a sub-component of the `mod` operation (they aren't the same). If you look in the GHC Base library you see `mod` tests for several conditions and adjusts the sign accordingly. (see `modInt#` in `Base.lhs`)
      singulars
      1. PO
      1. USThomas M. DuBuisson
    3. COAnother data point: I wrote a [quick Haskell translation of the C program](https://gist.github.com/1129054) without looking at @Hyperboreus's Haskell. So it's a bit closer to standard idiomatic Haskell, and the only optimization I added deliberately is replacing `mod` with `rem` after reading this answer (heh, oops). See the link for my timings, but the short version is "almost identical to the C".
      singulars
      1. PO
      1. USC. A. McCann
 

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