October 3, 2011 at 10:58 am
CELKO (10/3/2011)
Instead of writing procedural code, why not do it with declarative set-orientated code?
thanks for the post and script, celko.
does your question refer to writing a set-oriented solution when first presented with the problem, ie as the first iteration? or as a subsequent "efficientisation"?
if the former, the answer in my case is mainly because i would not know if my solution had satisfied the task at hand. this in turn is because i did not know enough about the problem itself, nor whether it could be done using tsql. if i had written a set-oriented solution as my first iteration, i would have had no idea whether or not it was doing what i wanted it to.
if the latter, the answer in my case is because i found it to be a more natural evolution to build procedural code for each iteration. this is because to me it was the most sure-fire way of getting the job done accurately, even if it wasn't getting the job done efficiently. imho, the time to think about efficiency for a task with unknowns like this is after i've proven that the task can be done.
just to be curious - did you write your script line by line as we see it now? or did you start in the middle and work your way out?
October 3, 2011 at 11:17 am
Hi,
"a repeat of the process" to me this means a recursive function, no?
In this case, it's definitely recursive and should be looked in base 2 format, where 10 (in base 10) is 1010 (in base 2). You'll have a resolution when the number has only one 1 in base 2, 100000000, 1000000, 10000, ....
You can know how many times you'll need to divide it by two to reach 1 by simply counting the number of 0 on the right side of the first 1 (in base 2). 64 is 1000000, you'll need to divide it 6 times (6 zeros on the right side of the 1).
10 is 1010, you'll divide it once and get an uneven number 101 (or 5) multiply by 3 + 1 give you 16 (always an even number) or 10000, which divides 4 times and you'll get 1. So you've divided it 5 times total.
40, which is 101000 can be divided three times and gives 5, or 101 *3 +1=16 or 10000, can be divided 4 times, so you've divided 9 times.
Pierre
October 5, 2011 at 7:12 am
I want to preface this by saying that I've not looked at this problem before and I'm sure the below is well known, but it is a fun little problem.
am still trying to come up with optimizations. the obvious (2^n) got to 1 in log2(n) steps gets us out of integer math with logs
I was looking at this from the other direction (e.g. What numbers lead to n0) And, as you note, x*(2^n) is the same path as x. I also noticed that if x mod 3 == 0 then there are no (odd) numbers leading in to the x*(2^n) path. This also leads me to the idea that we only need to look at odd numbers. So, looking at 9, we can say:
9 -> 7(2^2) -> 11(2^1) -> 17(2^1) -> 13(2^2) -> 5(2^3) -> 1(2^4)
A loop (which would be a disproof) would see a repeat of the odd number.
And since nothing leads to 9 (9 == 0 mod 3) this is a complete path[1] (ok 9(2^n) -> etc is a complete path).
This leads me to think that we only need to look at odd numbers where x == 0 mod 3, as those are complete paths.
So, it seems, for optimization of the original problem, that one would only need to test paths for odd X where X == 0 mod 3 [X = 3(2^n+1)]. We should keep track of all odd numbers to be able to shortcut the paths.
[1] The term complete path is (as far as I know) made up by me, but the idea almost certainly isn't new and it wouldn't surprise me if the term is used.
--
JimFive
October 7, 2011 at 9:27 am
On the philosophical point of "sometimes it's ok to start coding code right away", I don't find that contentious at all.
Our group has been doing Agile development for a while, and it encourages minimal upfront planning. The reason being is that you would often have a 'doh' moment no matter how much planning you do, and it's easier to adapt with a smaller design and less code, and you are apt to discover these things earlier, when it's easier to change things.
On the technical side using this for an example, recursion is quite limited in SQL. Recursion has the downside of requiring resources (usually memory in the form of a stack) for each iteration. So eventually it will run out of something. We had to change a recursive apporach to a loop approach on a SQL function ourselves.
But that is a good example of starting with one approach, and starting to code, then finding out you have to refactor it earlier on, without having to restructure and entire online shopping site!
Viewing 4 posts - 16 through 18 (of 18 total)
You must be logged in to reply to this topic. Login to reply