Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using Monads in C++ to Solve Constraints: 1. The List Monad

bartoszmilewski.com

Post reply on HN
Print view View original

41–50 of 73 posts

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#41

Post by dllthomas »

TheLoneWolfling wrote: post #39
dllthomas wrote: post #38

Earlier quoted context omitted.

Satisfying arbitrary constraints is often exponential ( http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ). I'd certainly be interested in seeing more efficient implementations, but the approach taken by the example Haskell code (and duplicated in your Python) is substantially more efficient than the example non-Haskell code provided in the article.

I know about BSAT / BIP / ILP / MLP and the problems thereof in the general case. However, this doesn't mean we have to punt the easy cases just because there are hard cases.

It certainly doesn't mean we have to punt the easy cases, but it seems inappropriate to lambaste the current solution without establishing that we are in fact looking at an easy case.

That no one seems to have produced (or pointed at) an asymptotically better solution in any language, I think that's some small evidence that there isn't such a solution and substantially more evidence that it's not easy to find.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#42

Post by TheLoneWolfling »

dllthomas wrote: post #41
TheLoneWolfling wrote: post #39

Earlier quoted context omitted.

I know about BSAT / BIP / ILP / MLP and the problems thereof in the general case. However, this doesn't mean we have to punt the easy cases just because there are hard cases.

It certainly doesn't mean we have to punt the easy cases, but it seems inappropriate to lambaste the current solution without establishing that we are in fact looking at an easy case. That no one seems to have produced (or pointed at) an asymptotically better solution in any language, I think that's some small evidence that there isn't such a solution and substantially more evidence that it's not easy to find.

There's an easy better method: assign variables starting from the lower order digits, greedily check correctness, and skip over all permutations with that prefix if it fails.

Although I don't know how one would go about proving or disproving if this is asymptotically better or just a (substantial) constant-factor speedup.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#43

Post by dllthomas »

TheLoneWolfling wrote: post #42
dllthomas wrote: post #41

Earlier quoted context omitted.

It certainly doesn't mean we have to punt the easy cases, but it seems inappropriate to lambaste the current solution without establishing that we are in fact looking at an easy case. That no one seems to have produced (or pointed at) an asymptotically better solution in any language, I think that's some small evidence that there isn't such a solution and substantially more evidence that it's not easy to find.

There's an easy better method: assign variables starting from the lower order digits, greedily check correctness, and skip over all permutations with that prefix if it fails. Although I don't know how one would go about proving or disproving if this is asymptotically better or just a (substantial) constant-factor speedup.

Oh! I had misread your original comment to be, "There are b! / (b - n)! ways to choose n of b unique numbers, [so] this solution is O(b^n)." You were contrasting! I believe that b!/(b-n)! is asymptotically the same class as b^n (whether we're varying b or n), hence my confusion.

I had initially skimmed the article, and assumed he was already handling uniqueness. With the correct definition of StateL, the solution presented is equivalent to what you describe here, but apparently that definition is deferred to a future article.

The idea would be that, for StateL, for_each would pick one value and pass that value to the lambda, interpreting the result in a context where the sel only sees the remaining values in the list.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#44

Post by dllthomas »

jordigh wrote: post #7
TheLoneWolfling wrote: post #2

This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n). That being said, it's still fast enough for this example. Also, Python solution along the same lines: import itertoolsdef def valueOf(*values, base=10): v = 0 for v in itertools.accumulate(values, lambda a,b: a*base+b): pass return v def solve(): for s,e,n,d,m,o,r,y in itertools.permutatio…

> This method is really inefficient. That's what I've noticed with Haskellers. They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down. A while ago I asked in #haskell for translations into Haskell of the following C++ code: http://codepad.org/sQTXhqC2 This should be easy. The algorithm is right in front of you. There should not be a lot of thinkin…

If, as per your profile, you are someone "who really just wants us all to get along", I would recommend against picking stupid fights like this.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#45

Post by TheLoneWolfling »

dllthomas wrote: post #43
TheLoneWolfling wrote: post #42

Earlier quoted context omitted.

There's an easy better method: assign variables starting from the lower order digits, greedily check correctness, and skip over all permutations with that prefix if it fails. Although I don't know how one would go about proving or disproving if this is asymptotically better or just a (substantial) constant-factor speedup.

Oh! I had misread your original comment to be, "There are b! / (b - n)! ways to choose n of b unique numbers, [so] this solution is O(b^n)." You were contrasting! I believe that b!/(b-n)! is asymptotically the same class as b^n (whether we're varying b or n), hence my confusion. I had initially skimmed the article, and assumed he was already handling uniqueness. With the correct definition of StateL, the solution pre…

> I believe that b!/(b-n)! is asymptotically the same class as b^n

Nope. It looks like it at first glance, but it isn't.

Look at what happens when n == b/C:

    b^(b/C) / (b!/(b - b/C)!) ==
    b^(b/C) / (b!/(b*(C-1)/C)!) ==
    e^(log(b^(b/C)) + log((b/C)!) - log((b*(C-1)/C)!)) ~=
    e^(b/C log(b) + [b*(C-1)/C] log (b*(C-1)/C) - [b*(C-1)/C] - b log b + b) ==
    e^((b+b (-1+C) log((-1+C)/C))/C) == 
    e^(b/C* (1+(C-1)log((C-1)/C)))
(I used Stirling's Approximation, namely the form ln(x!) ~= x ln x - x for large x)

However, note that (1+(C-1)log((C-1)/C)) / C is greater than zero for all C > 1, as 1+(C-1)log((C-1)/C) > 0 for all C > 1. As such, this diverges for all C > 1.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#46

Post by dllthomas »

TheLoneWolfling wrote: post #45
dllthomas wrote: post #43

Earlier quoted context omitted.

Oh! I had misread your original comment to be, "There are b! / (b - n)! ways to choose n of b unique numbers, [so] this solution is O(b^n)." You were contrasting! I believe that b!/(b-n)! is asymptotically the same class as b^n (whether we're varying b or n), hence my confusion. I had initially skimmed the article, and assumed he was already handling uniqueness. With the correct definition of StateL, the solution pre…

> I believe that b!/(b-n)! is asymptotically the same class as b^n Nope. It looks like it at first glance, but it isn't. Look at what happens when n == b/C: b^(b/C) / (b!/(b - b/C)!) == b^(b/C) / (b!/(b*(C-1)/C)!) == e^(log(b^(b/C)) + log((b/C)!) - log((b*(C-1)/C)!)) ~= e^(b/C log(b) + [b*(C-1)/C] log (b*(C-1)/C) - [b*(C-1)/C] - b log b + b) == e^((b+b (-1+C) log((-1+C)/C))/C) == e^(b/C* (1+(C-1)log((C-1)/C))) (I use…

b!/(b-n)! only = b!/(b/C)! when C = 2, but interesting regardless. I'll revisit when I have the chance.

In any case, I make the assertion that the algorithm proposed in the article is in fact O(b!/(b-n)!), with the intended definition of StateL.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#47

Post by TheLoneWolfling »

dllthomas wrote: post #46
TheLoneWolfling wrote: post #45

Earlier quoted context omitted.

> I believe that b!/(b-n)! is asymptotically the same class as b^n Nope. It looks like it at first glance, but it isn't. Look at what happens when n == b/C: b^(b/C) / (b!/(b - b/C)!) == b^(b/C) / (b!/(b*(C-1)/C)!) == e^(log(b^(b/C)) + log((b/C)!) - log((b*(C-1)/C)!)) ~= e^(b/C log(b) + [b*(C-1)/C] log (b*(C-1)/C) - [b*(C-1)/C] - b log b + b) == e^((b+b (-1+C) log((-1+C)/C))/C) == e^(b/C* (1+(C-1)log((C-1)/C))) (I use…

b!/(b-n)! only = b!/(b/C)! when C = 2, but interesting regardless. I'll revisit when I have the chance. In any case, I make the assertion that the algorithm proposed in the article is in fact O(b!/(b-n)!), with the intended definition of StateL.

Whoops, started with C = 2 and generalized, incorrectly it would seem. I'll edit it.

Edit: edited.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#48

Post by dllthomas »

TheLoneWolfling wrote: post #47
dllthomas wrote: post #46

Earlier quoted context omitted.

b!/(b-n)! only = b!/(b/C)! when C = 2, but interesting regardless. I'll revisit when I have the chance. In any case, I make the assertion that the algorithm proposed in the article is in fact O(b!/(b-n)!), with the intended definition of StateL.

Whoops, started with C = 2 and generalized, incorrectly it would seem. I'll edit it. Edit: edited.

Thanks :) C = 2 was enough, of course. So O(n!) is between O(k^n) and O(n^n)?

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#49

Post by TheLoneWolfling »

dllthomas wrote: post #48
TheLoneWolfling wrote: post #47

Earlier quoted context omitted.

Whoops, started with C = 2 and generalized, incorrectly it would seem. I'll edit it. Edit: edited.

Thanks :) C = 2 was enough, of course. So O(n!) is between O(k^n) and O(n^n)?

Yep. Though we often weaken a big Theta of n! to a big O of n^n, as it's easier to deal with.

Re: Using Monads in C++ to Solve Constraints: 1. The List Monad

#50

Post by dllthomas »

TheLoneWolfling wrote: post #49
dllthomas wrote: post #48

Earlier quoted context omitted.

Thanks :) C = 2 was enough, of course. So O(n!) is between O(k^n) and O(n^n)?

Yep. Though we often weaken a big Theta of n! to a big O of n^n, as it's easier to deal with.

That makes sense, and probably contributed to my confusion.
Post reply on HN