puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: spinoza1111 on 14 Jun 2005 23:01 Peter Ammon wrote: > spinoza1111(a)yahoo.com wrote: > > > > Peter Ammon wrote: > > > >>spinoza1111(a)yahoo.com wrote: > >> > >>>They also produce bad feeling in a classroom because of necessity they make only one student look "smart". > >>> > >> > >>irony...too big...crushing.... > > > > > > Why is this ironic? > > [...] > > > A puzzle generates one answer, along with resentment. > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > > What you wrote above is exactly what happened in this thread - and > that's the irony. Not a single poster here bothered to actually publish the XOR solution because of the stink of fear here created by corporate surveillance and its Benthamite possibility, and because some George Bush clone here might post nothing more than an online smirk, claiming superior knowledge without the ability to write. > > -Peter
From: spinoza1111 on 15 Jun 2005 03:14 Christopher Barber wrote: > spinoza1111(a)yahoo.com wrote: > > > > Christopher Barber wrote: > > > >>spinoza1111(a)yahoo.com wrote: > >> > >>>Christopher Barber wrote: > >>> > >>> > >>>>spinoza1111(a)yahoo.com wrote: > >>>> > >>>> > >>>> > >>>>>>>For, I used the phrase "close to" as regards O(n). > >>>>>>> > >>>>>>>O(n*n) == O(n*n/2), of course. But it's also the case for practical > >>>>>>>applications that n*n/2 < n*n. > >>>>>> > >>>>>>Sure, given the choice between an algorithm that costs n*n steps and one that > >>>>>>costs n*n/2 steps of the same size, the latter is a better choice in terms of > >>>>>>cost, but I don't known anyone other than you that would call such an > >>>>>>algorithm "close to" O(n). When there are linear and O(n log n) algorithms > >>>>>>that are also simpler to implement, what is the practical use case for your > >>>>>>algorithm? > >>>>> > >>>>>Read the literature on O(x), for Chrissake. See for example Skiena, The > >>>>>Algorithm Design Manual > >>>>>(http://www.amazon.com/exec/obidos/tg/detail/-/0387948600/qid=1118630635/sr=8-3/ref=pd_csp_3/103-4992382-6347852?v=glance&s=books&n=507846). > >>>>> > >>>>>You don't UNDERSTAND O(x) UNTIL you know when to use O(n^2) in the > >>>>>pragmatic sense where n is small and known to be small for practical > >>>>>applications. > >>>> > >>>>You are right that it can be ok to use a suboptimal algorithm for when you > >>>>know for a fact that the data size will be small, but generally you would only > >>>>do so because the faster algorithm is more complex or more work to implement. > >>>>This is not the case with your algorithm. > >>> > >>>How do you know that for a specific instance? In a specific instance, > >>>the preconditions may indeed be that n is bounded and delete is fast. > >>>In a specific instance, you have to know how to work with (write about: > >>>speak of) algorithms without snap moral judgements based on > >>>ill-understood complexity theory. > >> > >>First, if delete has constant cost then your algorithm is O(n^2). If delete > >>is O(n), then your algorithm is O(n^3), so the cost of delete doesn't really > >>matter. > >> > >>Second, the "trick" solution is simple to implement (provided you are using a > >>non-crappy programming languge) and is O(n), but even without XOR you can code > >>an O(n) solution using hash tables or a large bit array. > >> > >>Third, assuming you have a system-supplied sort function, the sort and search > >>solution is O(n log n) and still easier to implement. > >> > >>Finally, your algorithm isn't even the simplest O(n^2) algorithm! > >> > >>for (i=0; i<max; ++i) { > >> for (j=0; j<max; ++j) { > >> if (i !=j && a[i] == a[j]) break; > >> } > >> if (j == max) return a[i]; > >>} > > > > > > Might be simple is not very elegant, since it wastes time, > > Of course it wastes time. It is O(n^2)! No, your understanding of big O is deficient because big O doesn't show you that an algorithm "wastes time" (where the moral implication is that the algorithm is a bad, Commie, terrorist, child molestor algorithm). If unlike here there is no O(n) algorithm then the O(n^2) doesn't "waste time". If there is, but n is roughly less than 10e2 then it's a waste of time to develop the code for the O(n) algorithm if that code is complex. > > > in the outer > > loop, on elements that have already been paired. Needs to delete. And, > > only has one operation inside the inner loop. > > > > Are you even AWARE that one way to improve a loop within the overbroad > > categories of algorithm complexity is to move paired operations in the > > loop as I did? Sounds like you need to supplement your education with > > some knowledge of compiler optimization, in which code improvements are > > made in the small but make in aggregate a genuine contribution. > > Why bother with optimizing a bad algorithm? The only time you would use > such an algorithm is when n is very small so there is no need to perform > any other optimizing tricks. When n is large you had better be using > an O(n) algorithm. This is what optimizing compilers do, mate. And in software maintenance you need to know how to make low-risk code improvements to "bad", Commie, terrorist, child molestor algorithms. There are no "bad" algorithms just as there are no bad dogs. > > > I agree that an O(log n) algorithm is in some nonmoral sense better > > than O(n), which is better than O(n^y)! But in real programming there's > > much more to know. > > Like what? > > Your algorithm doesn't appear to have any practical use and you have yet > to suggest one. What IS of practical use to me is the ability to discourse wittingly and in an amusing fashion about the actual properties of real software. > > >>>>You appear to have "misread" me. I just meant that it was not obvious > >>> > >>>>from what you posted *previously* that you understood the O() notation. > >>> > >>>Sorry you got that impression. But in a collegial setting, you'd assume > >>>that discussants understood the material and you wouldn't have to waste > >>>time establishing their bonafides. > >> > >>I would not assume that someone understood if they said something that > >>made it seem otherwise. That was the case here. When you suggested your > >>O(n^2) was "close to" O(n), you used language that I and others have never > >>heard used when speaking of the O() notation, so the assumption of prior > >>knowledge was dropped. > > > > The problem is that you seem more concerned with biography than > > anything else. OK, the terminology is unfamiliar. > > It is not the terminology that is unfamiliar, it is your non-standard use of > it. I have never heard anyone speak of an O(n^2) algorithm as being "close > to" an O(n) one in performance. I have no idea what you mean by "biography". Then you are unread, for when n<10e1 the O(n) and O(n^2) algorithms are "close" in significant cases. By "biography" I mean wasting time in code reviews and here with an attack on the speaker's or poster's professional biography. Basically, human dignity and economic good sense should require that no-one on a job of work should be either permitted or required to establish his right to be a part of a dialog. The "biographical" approach wastes time in attacks on competence and knowledge. The Harvard law professor Roberto Unger shows how American law, in the absence of a coherent theory of natural rights, biases our politics into negative campaigning and as far as I can tell, Unger's use of "biography" names that nihilism which in failing to credit abstract principles has only negative biography to rely on in making judgements. > > > Hey, how did you do > > in calculus and the notion of limit of a function? > > Of course, but that does not apply to this topic. As n increases the > performance of O(n) and O(n^2) algorithms will diverge. And as it decreases the performance will converge. > > > Perhaps there is a whole field of algorithm dynamics in which the > > properties of algorithms are studied as they change between different > > versions of the algorithm. > > I am not sure what you mean, but those who study algorithms do examine > their properties under different conditions. > > > Probably not. But one reason for the 80% failure rate of enterprise > > systems is the unwillingness to speak of code without snap judgements > > and one-upmanship in a field that has been RUINED by laissez faire > > "competition". > > I don't think anyone here made a "snap judgement". I also don't see > how suggesting improvements to algorithms or program designs is going > to lead to failures in enterprise systems. Not in itself. But failure to review because everybody's pulling their pud does cause failures. > > > And even if it makes no sense to speak of the execution time of a > > program approaching a limit, becoming "close to O(n)", approaching an > > infinitesimal but nonzero value for larger N, note that there's a whole > > field of code improvement within compiler optimization in which the > > improvements are beneath the radar screen of complexity theory. > > There is no such thing as an infintesimal integer value. It is also not No, but there are small integer values. > interesting to claim that algorithms tend to converge in performance as the > sample size goes down because all algorithms are going to perform just about > the same for n == 0. By this argument, an O(n^n) algorithm is "close to" > O(n)! You're not interested in trivial, degenerate, null cases because as a non-mathematician, as at best a techie, you view those cases as members of a bogus moral category. A REAL mathematician, such as Nash, remains I think until the end of his life interested in the fact that when you multiply by 0, you get 0: that when you multiply n times 1, you get n. My own experience is that a program that fails for either zero or one input is a bad program insofar as its text fails thereby to be a recursive proof of the program's correctness. You want to see in some informal sense that if you assume the program correct for n, it must be correct for n+1, and you want to make sure the program works for n=0. But entirely too many programmers have been led by a superficial mathematics, taught as a series of plausibly deniable moral judgements, that as grown-ups, they need not worry about n=0 or 1. > > I don't really know what you are talking about w/ regard to compiler > optimization, but based on this discussion I wouldn't want you optimizing our > compiler. Note how you reduce everything to the lower-middle class anxiety of who has a job. And note that given your responses, I am not interested in working with you. > > > I'm a happy camper who likes to solve problems. > > You don't give the appearance of being a "happy camper", and if you are > so into solving problems then why are you so resistant to admitting that > there might be better algorithms for the problem at hand? > > > But I also like to fight with people who deal with their own > > feelings of incompetence by transferring them onto innocent bystanders. > > I don't know who you are taking about, but it isn't me. Excuse me, you've been harassing me in this thread since day one. > > - Christopher
From: Gerry Quinn on 15 Jun 2005 05:36 In article <1118819658.158795.23850(a)o13g2000cwo.googlegroups.com>, spinoza1111(a)yahoo.com says... > If unlike here there is no O(n) algorithm then the O(n^2) doesn't > "waste time". If there is, but n is roughly less than 10e2 then it's a > waste of time to develop the code for the O(n) algorithm if that code > is complex. Complex as in: int answer = 0; for ( int i = 0; i < array.size(); i++ ) { answer ^= array[ i ]; } // answer is the unique integer - Gerry Quinn
From: CBFalconer on 15 Jun 2005 09:02 spinoza1111(a)yahoo.com wrote: > .... snip ... > > Not a single poster here bothered to actually publish the XOR > solution because of the stink of fear here created by corporate > surveillance and its Benthamite possibility, and because some > George Bush clone here might post nothing more than an online > smirk, claiming superior knowledge without the ability to write. No, because the original poster of that deserves the credit for his ingenuity, and meanwhile some unnamed jokers around here have been raving on about all sorts of imaginary foolishness and drowning out any on-topic and serious discussions of anything. They should probably take their lithium pills. -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson
From: spinoza1111 on 15 Jun 2005 10:31
CBFalconer wrote: > spinoza1111(a)yahoo.com wrote: > > > ... snip ... > > > > Not a single poster here bothered to actually publish the XOR > > solution because of the stink of fear here created by corporate > > surveillance and its Benthamite possibility, and because some > > George Bush clone here might post nothing more than an online > > smirk, claiming superior knowledge without the ability to write. > > No, because the original poster of that deserves the credit for his > ingenuity, and meanwhile some unnamed jokers around here have been > raving on about all sorts of imaginary foolishness and drowning out > any on-topic and serious discussions of anything. They should > probably take their lithium pills. (1) The OP didn't display any such ingenuity because the strategy here has to be, being silent about knowledge and making reference to it. We have no idea whether the OP developed the XOR solution. (2) There is absolutely no reason in a WRITTEN network for the solution not be published alongside the creative and thought-provoking posts of your *namenlosen* Till Eulenspiegel because literally, nothing is drowned out, much as control freaks would like to shout people down, and despite their secret longings for the oral regression of the thug. (3) You need your wise-up pill because there is, as I have said, no reason to think that the OP knew the solution *ab initio* and didn't steal it from a book, nor that the XOR-suggestors knew exactly how, in hell, to implement the solution. They remain intimidated by a Benthamite culture of corporate surveillance and a core membership of trolls. Have a nice day. > > -- > "If you want to post a followup via groups.google.com, don't use > the broken "Reply" link at the bottom of the article. Click on > "show options" at the top of the article, then click on the > "Reply" at the bottom of the article headers." - Keith Thompson |