 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html
Oh, *that's* fizzbuzz? Hmm, OK.
Also... that's really kinda scary. o_O Let's hope plumbers are better...
uh... hmm, OK, maybe not. Well let's hope to **** that medical
professionals are better! O_O
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] dev null> wrote:
> http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html
As I have commented previously somewhere, I have heard about this here
as well. What's worse, at least in the past companies actually hired people
for programming positions just on the basis that those people *claimed* to
be competent programmers even though they hadn't ever written a single line
of code.
Why do people apply to programming jobs even though they have no experience
whatsoever? My guess is that their rationale goes like: "I need a job badly.
Programming is really easy; heck, even kids can do it, so how hard can it be?
I'll ensure the job first, and learn the programming part later. It'll
probably take just a week or two."
On a side note, interviewers should, on the other hand, be careful with
what they consider "trivial" assignments. Sometimes a problem might sound
quite easy and trivial, when in fact it isn't.
As an example, the basic principle between binary searching (searching an
element in a sorted array in O(log n) time) sounds quite trivial. However,
it's surprisingly difficult to implement correctly.
Take 100 experienced, competent programmers and give them the task of
implementing binary search on paper in the programming language they are
most fluent with, and perhaps 5 of them will give you a correct
implementation. (The rest will fail in some cases mostly due to off-by-one
errors.) A correct implementation requires surprising amounts of attention
to detail, and a quick&dirty naive implementation will most probably be
incorrect. And this for a piece of program that requires maybe 10 lines of
code at most.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> As I have commented previously somewhere, I have heard about this here
> as well. What's worse, at least in the past companies actually hired people
> for programming positions just on the basis that those people *claimed* to
> be competent programmers even though they hadn't ever written a single line
> of code.
I don't think this is unique to programming. From what I've seen, most
managers get hired based on their ability to spout impressive-sounding
BS rather than their ability to actually manage a department.
> Why do people apply to programming jobs even though they have no experience
> whatsoever? My guess is that their rationale goes like: "I need a job badly.
> Programming is really easy; heck, even kids can do it, so how hard can it be?
> I'll ensure the job first, and learn the programming part later. It'll
> probably take just a week or two."
I would imagine that quite a few of then know damned-well that they
can't program, and expect to be able to just con somebody into hiring
them. I imagine this is the same for every profession.
The difference is that if, say, you claim to be a brick layer, and they
ask you to build a small wall, and it looks like a piece by Picasso,
then you don't need to be an expert builder to tell that this person is
lying out of their arse. On the other hand, a broken program doesn't
look "obviously" different to a working program. An expert can tell
immediately, but to the casual observer, it's not so clear. So it's
harder to tell whether somebody can program.
In a similar vein, there's probably a greater opportunity for
self-delusion. If you try to build a wall and it's rubbish, you start to
realise that building a wall is far more complicated than you expected.
But if your program doesn't compile... it there just some small thing
you need to fix? Or is it because your code is gibberish?
I'm sure I must have told you the tale of the MSc student who begged me
to "fix me Java, yah?" He claimed it was nearly working, but it just
needed a few small tweaks. So I sat down and read his "Java". What he
had written was a bunch of Java language keywords, lots of curly
brackets, nice indentation, but... IT WAS NONESENSE! It wasn't Java. It
was gibberish that bore a superficial resemblance to Java. Lots of
hopeful-sounding variable names, but not even approaching being
syntaxually correct.
To this day, I'm genuinely not sure whether the guy was just writing
gibberish and hoping to bluff his way through (or get somebody to do it
for him), or whether he actually believed his code was nearly correct...
Finally, if you sculpt a work of art, everybody looks at that and goes
"oh, that's great, it must have been really hard to make that". It's not
nearly so obvious that programming is hard. (Especially when vendors
keep trying to sell whizzy tools that make it all "easy" for "anybody to
do".)
> On a side note, interviewers should, on the other hand, be careful with
> what they consider "trivial" assignments. Sometimes a problem might sound
> quite easy and trivial, when in fact it isn't.
If the interviewer asks you to solve the Travelling Salesman Problem so
that it can find a route between 500 cities in just a few seconds, you
probably don't want to work for them. ;-)
> As an example, the basic principle between binary searching (searching an
> element in a sorted array in O(log n) time) sounds quite trivial. However,
> it's surprisingly difficult to implement correctly.
>
> Take 100 experienced, competent programmers and give them the task of
> implementing binary search on paper in the programming language they are
> most fluent with, and perhaps 5 of them will give you a correct
> implementation. (The rest will fail in some cases mostly due to off-by-one
> errors.) A correct implementation requires surprising amounts of attention
> to detail, and a quick&dirty naive implementation will most probably be
> incorrect. And this for a piece of program that requires maybe 10 lines of
> code at most.
Hmm, OK. This doesn't sound especially hard. So let me see if I can
implement it, and then everybody can laugh at how badly I got it wrong...
find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
find field target array (base,size)
| size < 0 = error "invalid subrange size"
| size == 0 = Nothing
| size == 1 = if field (array ! base) == target then Just (array !
base) else Nothing
| otherwise = find field target array (base, size `div` 2)
`mappend` find field target array (base + size `div` 2, size `div` 2)
Now I suppose I better go run that and see if it actually works.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
> find field target array (base,size)
> | size < 0 = error "invalid subrange size"
> | size == 0 = Nothing
> | size == 1 = if field (array ! base) == target then Just (array !
> base) else Nothing
> | otherwise = find field target array (base, size `div` 2) `mappend`
> find field target array (base + size `div` 2, size `div` 2)
>
> Now I suppose I better go run that and see if it actually works.
Well, the final line is wrong for a start. (Due to rounding, if the
array size isn't even, one element gets elided from the search.)
| otherwise =
let size2 = size `div` 2
in find field target array (base, size2) `mappend` find field
target array (base + size2, size - size2)
That should work better. The division of a range into two subranges is
still unequal, but at least all elements are included now...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html
I few clicks away from this, I got to here:
http://www.eis.mdx.ac.uk/research/PhDArea/saeed/paper1.pdf
I don't know about you, but *I* have always wondered why some people
find programming hard. It is a "well known" fact that there seem to be
two types of students: those who "get" programming, and find
introductory courses ridiculously easy, and those do "don't get"
programming, and find even the simplest exercises insummountably difficult.
I haven't finished reading this paper yet, but it throws some
interesting ideas out there. One particular paragraph leaps out at me:
"Putnam and others found that novices’ misconceptions about the
capabilities of computers could have a massive negative impact on their
success at programming. Many of their subjects tried to use meaningful
names for their variables, apparently hoping that the machine would be
able to read and understand those names and so perceive their intentions."
Oh I have *so* seen this! People who seem to think that if they write
their code with obvious-enough names and syntax that's near-enough to
being correct, the computer will "just know" what they mean. They fail
to grasp that the syntax must be EXACTLY CORRECT, even if it seems silly
or unnecessary.
I guess it's because they're used to talking to humans. If you say
something to a human with somewhat incorrect grammer (or even
horrifyingly broken grammer), they can usually still figure out what you
mean.
Computers are far, far more stupid than humans. But decades of advances
in computing technology have brought us to the point where computers
*look clever*, even though they aren't. I suspect this might be why some
people have trouble learning to *use* a computer too.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html
>
> Oh, *that's* fizzbuzz? Hmm, OK.
>
> Also... that's really kinda scary. o_O Let's hope plumbers are better...
> uh... hmm, OK, maybe not. Well let's hope to **** that medical
> professionals are better! O_O
the real problem is that many people who should really be plumbers or medicals
are into programming careers. well, plumbing may still have its uses... :)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Also... that's really kinda scary. o_O Let's hope plumbers are better...
>> uh... hmm, OK, maybe not. Well let's hope to **** that medical
>> professionals are better! O_O
>
> the real problem is that many people who should really be plumbers or medicals
> are into programming careers. well, plumbing may still have its uses... :)
Well, hey, at least getting programming wrong doesn't kill people...
...oh, wait:
http://en.wikipedia.org/wiki/Therac-25
Hmm. Oh dears.
Well, at least if a plumber or medical person does their job wrong, you
can get compensation? :-}
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> the real problem is that many people who should really be plumbers or medicals
> are into programming careers. well, plumbing may still have its uses... :)
One could argue that The Real Problem(tm) is that IDE vendors keep
claiming to have made programming "easy" now. ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> be competent programmers even though they hadn't ever written a single line
> of code.
I usually ask them to print out the prime numbers less than 100 or something.
> On a side note, interviewers should, on the other hand, be careful with
> what they consider "trivial" assignments.
Yeah. I had one that was something like "print the lowest N values from a
binary tree, in C". When's the last time I did recursion in C? And doing it
over the phone? Bleh.
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> nemesis wrote:
>
> > the real problem is that many people who should really be plumbers or medicals
> > are into programming careers. well, plumbing may still have its uses... :)
>
> One could argue that The Real Problem(tm) is that IDE vendors keep
> claiming to have made programming "easy" now. ;-)
still waiting for the magical "Make Solution" button... ;)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
> find field target array (base,size)
> | size < 0 = error "invalid subrange size"
> | size == 0 = Nothing
> | size == 1 = if field (array ! base) == target then Just (array !
> base) else Nothing
> | otherwise =
> let size2 = size `div` 2
> in find field target array (base, size2) `mappend` find field target
> array (base + size2, size - size2)
I don't know Haskell, but my best guess at understanding this code looks
like you're always recursing into both sides, without actually doing the
comparison of the center element to the target element. So you're not
saving any time, and you would get faster results with a linear search.
But maybe I just don't understand the language well enough to see the
comparison.
- Slime
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> writes:
> Warp wrote:
> I usually ask them to print out the prime numbers less than 100 or something.
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 91, 97]
for prime in prime:
print prime
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Slime wrote:
> > find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
> > find field target array (base,size)
> > | size < 0 = error "invalid subrange size"
> > | size == 0 = Nothing
> > | size == 1 = if field (array ! base) == target then Just (array !
> > base) else Nothing
> > | otherwise =
> > let size2 = size `div` 2
> > in find field target array (base, size2) `mappend` find field target
> > array (base + size2, size - size2)
>
> I don't know Haskell, but my best guess at understanding this code looks
> like you're always recursing into both sides, without actually doing the
> comparison of the center element to the target element.
Oh... my god... >_<
I blame Warp. I was so busy making sure that there's no off-by-one
errors that I totally forgot to actually, you know, IMPLEMENT THE RIGHT
ALGORITHM!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
OK, 3rd time lucky: let's see if I can actually implement this thing
correctly. :-P
find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
find field target array (base,size)
| size < 0 = error "invalid subrange size"
| size == 0 = Nothing
| size == 1 = if field (array ! base) == target then Just (array !
base) else Nothing
| otherwise =
let
size2 = size `div` 2
base2 = base + size2
in
case compare (field (array ! base2)) target of
EQ -> Just (array ! base2)
GT -> find field target array (base, size2)
LT -> find field target array (base + size2, size - size2)
Now, finally, it should work. (But I've said that twice before already...)
Damnit, no wonder nobody loves me. :-(
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Damnit, no wonder nobody loves me. :-(
Implementing a binary search in Haskell is now a prerequisite for love?
That's news to me :-)
--
Vincent
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Damnit, no wonder nobody loves me. :-(
>
> Implementing a binary search in Haskell is now a prerequisite for love?
> That's news to me :-)
I meant the fact that I'm mentally retarded rather than specifically
that I wrote this program wrong.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> I don't think this is unique to programming. From what I've seen, most
> managers get hired based on their ability to spout impressive-sounding BS
> rather than their ability to actually manage a department.
It all comes down to how competent the people are that are interviewing. If
a company is already full of BS managers then of course they are going to
employ more BS staff and the problem will never improve (I know two people
that work at a company like this). Alternatively, if you have a good set of
people already in charge, interviewing and making hiring decisions, you are
not going to employ any BS managers (or programmers) in the first place.
> I would imagine that quite a few of then know damned-well that they can't
> program, and expect to be able to just con somebody into hiring them. I
> imagine this is the same for every profession.
Exactly. At said company I mentioned before, it's usually the one who asks
for the least money that gets hired (or who already knows one of the
managers well), nothing to do with how skilled they are or how much
experience they have.
> If the interviewer asks you to solve the Travelling Salesman Problem so
> that it can find a route between 500 cities in just a few seconds, you
> probably don't want to work for them. ;-)
If I were interviewing I'd ask which languages they know, lock them in a
room with a machine with a language installed they don't know (plus relevant
learning material), and see how many project euler problems they can
complete in 24 hours :-)
>> Take 100 experienced, competent programmers and give them the task of
>> implementing binary search on paper in the programming language they are
>> most fluent with, and perhaps 5 of them will give you a correct
>> implementation. (The rest will fail in some cases mostly due to
>> off-by-one
>> errors.)
I can believe that, but then does that make someone a bad programmer if they
can't get an algorithm like that exactly right on paper first time?
Personally I would prefer someone who "gets" the idea and could roughly code
it very quickly, then test it and quickly identify modifications needed to
get it working. The alternative is someone who either spends 30 minutes
painstakingly figuring it out in their head, or the one who just recites it
because he's done it before recently. I would follow it up with some subtle
modification requests (eg how to make it more cache friendly, or how to
efficiently deal with data sets bigger than RAM) to see their thought
process for something new.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> I don't think this is unique to programming. From what I've seen, most
>> managers get hired based on their ability to spout impressive-sounding
>> BS rather than their ability to actually manage a department.
>
> It all comes down to how competent the people are that are
> interviewing.
Yeah, that seems to be it.
Or perhaps how seriously the management take the interviewer's opinion.
I've heard of people getting hired even though the person who
interviewed them said they were rubbish. Obviously, this shouldn't ever
happen. (Why did you bother interviewing them??)
> If a company is already full of BS managers then of
> course they are going to employ more BS staff and the problem will never
> improve.
This appears to be how the entire world works, as best as I can tell.
> Alternatively, if you have a good set of people already in charge,
> interviewing and making hiring decisions, you are not going to employ
> any BS managers (or programmers) in the first place.
I haven't seen that happen yet, but I live in hope.
>> I would imagine that quite a few of then know damned-well that they
>> can't program, and expect to be able to just con somebody into hiring
>> them. I imagine this is the same for every profession.
>
> Exactly.
Like I said, I think the difference is that in something abtract like
programming, it's easier to pretend that you know what you're doing. If
somebody asks you to build a wall and you can't, it's pretty obvious. ;-)
> At said company I mentioned before, it's usually the one who
> asks for the least money that gets hired (or who already knows one of
> the managers well), nothing to do with how skilled they are or how much
> experience they have.
Ouch. Management short-sightedness appears to be without limit.
> If I were interviewing I'd ask which languages they know, lock them in a
> room with a machine with a language installed they don't know (plus
> relevant learning material), and see how many project euler problems
> they can complete in 24 hours :-)
Ooo, that's harsh, man! Some of those are wicked-hard...
I'm trying to think of a language you could actually throw at me that I
don't know, but then I realised it's actually not hard: C, Perl, Python,
PHP, Bash, Ruby, VB, C#, F#, Erlang, any of those would fit the bill. o_O
>>> Take 100 experienced, competent programmers and give them the task of
>>> implementing binary search on paper in the programming language they are
>>> most fluent with, and perhaps 5 of them will give you a correct
>>> implementation.
>
> I can believe that, but then does that make someone a bad programmer if
> they can't get an algorithm like that exactly right on paper first time?
> Personally I would prefer someone who "gets" the idea and could roughly
> code it very quickly, then test it and quickly identify modifications
> needed to get it working.
Mmm, true... It's especially hard to code on paper, without a real
computer to test it with.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Darren New <dne### [at] sanrrcom> writes:
>> I usually ask them to print out the prime numbers less than 100 or something.
>
> primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 91, 97]
> for prime in prime:
> print prime
primes = f [2..] where f (p:xs) = p : [ x | x <- xs, x `mod` p > 0]
print (take 100 primes)
It's pretty much a standard incantation that most Haskellers will know
off the top of their heads. Of course, it's horrifyingly inefficient for
generating large numbers of primes, but for just the first 100...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Alternatively, if you have a good set of people already in charge,
>> interviewing and making hiring decisions, you are not going to employ any
>> BS managers (or programmers) in the first place.
>
> I haven't seen that happen yet, but I live in hope.
Funny, the companies I've worked at, plus the customers I've dealt with all
seem to work this way. I guess the ones that are rubbish don't get much
business, or if they do nobody comes back!
> Like I said, I think the difference is that in something abtract like
> programming, it's easier to pretend that you know what you're doing. If
> somebody asks you to build a wall and you can't, it's pretty obvious. ;-)
Personally I think it's pretty obvious if someone asks you to write a
program to show the first 1000 prime numbers, and you can't. Even a
non-programmer would recognise that it wasn't working.
> Ooo, that's harsh, man! Some of those are wicked-hard...
Yeh I'm just getting back in to doing some more of them. Funny how just 6
or 12 months later you come back and some that seemed wicked hard are
suddenly easy!
> I'm trying to think of a language you could actually throw at me that I
> don't know, but then I realised it's actually not hard: C, Perl, Python,
> PHP, Bash, Ruby, VB, C#, F#, Erlang, any of those would fit the bill. o_O
I guess it also depends on what sort of job you want the person to do. Do
you want them to be a C++ code-monkey for their entire career at your
company, or are you looking for someone to do a bit more. This will
determine whether you simply test their C++ skills or find some other way to
test them with unfamiliar languages and problems.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Alternatively, if you have a good set of people already in charge,
>>> interviewing and making hiring decisions, you are not going to employ
>>> any BS managers (or programmers) in the first place.
>>
>> I haven't seen that happen yet, but I live in hope.
>
> Funny, the companies I've worked at, plus the customers I've dealt with
> all seem to work this way. I guess the ones that are rubbish don't get
> much business, or if they do nobody comes back!
Apparently I'm applying to the wrong people...
(Actually, that's not true. I'm not applying to *anybody*. :-( But
that's another story.)
>> Like I said, I think the difference is that in something abtract like
>> programming, it's easier to pretend that you know what you're doing.
>> If somebody asks you to build a wall and you can't, it's pretty
>> obvious. ;-)
>
> Personally I think it's pretty obvious if someone asks you to write a
> program to show the first 1000 prime numbers, and you can't. Even a
> non-programmer would recognise that it wasn't working.
Sure, you'd think. But if you try to run it and it fails, you can spout
some gibberish about "oh, it's a system incompatibility" or "yeah, it's
a known bug in the new GCC release" or "ah yes, I'm used to working with
RedHat. Under SuSE there's a known glitch with glibc that can sometimes
make this happen" or any number of other BS excuses.
And, if the person doing the interviewing is some PHB, they'll sit there
and be like "wow, this guy really knows is stuff!" (And they'll also
completely ignore the tech dude sitting next to them going "uh, sir,
this guy is talking utter crap!")
>> Ooo, that's harsh, man! Some of those are wicked-hard...
>
> Yeh I'm just getting back in to doing some more of them. Funny how just
> 6 or 12 months later you come back and some that seemed wicked hard are
> suddenly easy!
It's all about using the right abstractions. ;-) Some of the hardest
programs of science and mathematics turn out to actually be trivial to
solve once you already know how to solve it.
>> I'm trying to think of a language you could actually throw at me that
>> I don't know, but then I realised it's actually not hard: C, Perl,
>> Python, PHP, Bash, Ruby, VB, C#, F#, Erlang, any of those would fit
>> the bill. o_O
>
> I guess it also depends on what sort of job you want the person to do.
> Do you want them to be a C++ code-monkey for their entire career at your
> company, or are you looking for someone to do a bit more. This will
> determine whether you simply test their C++ skills or find some other
> way to test them with unfamiliar languages and problems.
And that of course depends on what your company does. If you have a
deployed application with 82 MLOC written in C++ and you just want
somebody to maintain it, you'd better hope they know their C++. If on
the other hand you want somebody to throw together a few housekeeping
scripts, flexibility is probably more important.
And if you want somebody to design and build mathematical models, what
programming languages they know is going to be utterly irrelevant - but
you'd better hope to God they have a good grasp of algebra!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Neeum Zawan <fee### [at] festercom> wrote:
> primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 91, 97]
> for prime in prime:
> print prime
Way to overcomplicate a simple problem. Why not simply:
print 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 91, 97
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
> find field target array (base,size)
> | size < 0 = error "invalid subrange size"
> | size == 0 = Nothing
> | size == 1 = if field (array ! base) == target then Just (array !
> base) else Nothing
> | otherwise =
> let
> size2 = size `div` 2
> base2 = base + size2
> in
> case compare (field (array ! base2)) target of
> EQ -> Just (array ! base2)
> GT -> find field target array (base, size2)
> LT -> find field target array (base + size2, size - size2)
Btw, "binary search" all in itself is an ambiguous concept, as it may mean
one of several things depending on the specification:
1) The algorithm tells whether the element exists in the array or not
(in other words, the return value is a boolean).
2) The algorithm returns either the found element itself (if it is in the
array) or an index/reference to the element. If there are many elements which
compare equal, it returns one of them.
3) Like the previous, but if there are many elements which compare equal,
it returns the first one, or the index/reference to the first one.
Why the difference between 2) and 3) is relevant may not be immediately
obvious, but there are many cases where it is. For example, while the elements
may compare equal, they might have ancillary data that is different (iow.
each element is a key/value pair, where the key is used for the ordering).
Thus it makes a difference which element is returned.
Also, if an index/reference is returned, it can make a significant
difference whether it's pointing to the first element in a series of equal
elements, or a random element among them. In many algorithms it's important
to get the first element.
Changing the algorithm so that it always returns an index to the first
element of a range of equal elements (if they are what is being searched)
doesn't change the algorithm much, and it will still be O(log n).
Sometimes you want the last element in the range of equal values instead,
or even an index to the one-past the last. One obvious use for this is if
instead of wanting just one of the equal elements, you want to know the
whole range. This is often useful.
So let's see if you can modify the algorithm to conform to the spec:
"A function which takes an array of sorted elements and a value, and
which returns an index to the first element in the array which is not
smaller than the value, or to the end of the array if the value is larger
than any of the array elements, in O(log n)."
The algorithm is pretty much the same as the basic "naive" algorithm.
It just requires a tiny bit of fine-tuning.
And just a slightly more complicated:
"A function which takes an array of sorted elements and a value, and
which returns an index pair. The first index points to the first element
in the array which is not smaller than the value. The second index points
to the first element in the array which is greater than the value. Naturally
If the value is greater than all the array elements, they both will point
to the end of the array. And naturally all this in O(log n)."
As stated, getting the range of equal values is sometimes very useful,
which is why it's important to know how to do this.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp <war### [at] tagpovrayorg> writes:
> Neeum Zawan <fee### [at] festercom> wrote:
>> primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 91, 97]
>> for prime in prime:
>> print prime
>
> Way to overcomplicate a simple problem. Why not simply:
>
> print 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 91, 97
Because I wanted one prime per line.
(Whew! Glad no one pointed out that my code doesn't work!)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
