Re: Searching missing number in large data.
- From: Nigel Thomas <nigel.cl.thomas@xxxxxxxxxxxxxx>
- To: Will Morgan <wmorgan@xxxxxxxxxxxxxxxxx>, "abhishek.gurung" <abhishek.gurung@xxxxxxxxxxx>
- Date: Wed, 19 May 2010 16:31:12 +0100
32k vs 2^^32 - oops, my bad, thanks for pointing it out.
No explicit need to sort, but there is a need to read all the numbers
(sounds linear to me).
A conceptually simple method - set up a 4Gb bit array (eg an array of
134 million 32bit words) and use it to mark off each number as it
arrives. At end of list, scan the bit array to find the first
un-marked bit (which would be one of the bits in the first
non-#FFFFFFFF word). Clearly both of these phases are O(N); depending
on how the numbers are delivered, the slowest part may well be reading
them in...
The only way I can see this becoming O(logN) is to add another much
slower phase of order logN which swamps the linear phases...
Cheers Nigel
2010/5/19 Will Morgan <wmorgan@xxxxxxxxxxxxxxxxx>:
> Actually he said 2^32 numbers
>
> So... a list of 4,294,967,296 unordered numbers.
>
> Just ordering the list will take O(log N) or worse I'd think. I know it can
> be done in linear time.
>
> Don't know if you can find a missing number in an unordered list - and I
> don't know how you would sort it in better than linear time.. then again I
> haven't needed to work with algorithms much in a *long* time.
>
> Where does such a question come from? Academia and/or some kind of critical
> thinking check/test are my only thoughts here.
>
>
> -----Original Message-----
> From: oracle-l-bounce@xxxxxxxxxxxxx [mailto:oracle-l-bounce@xxxxxxxxxxxxx] On
> Behalf Of Nigel Thomas
> Sent: Wednesday, May 19, 2010 8:08 AM
> To: Oracle Freelist
> Subject: Re: Searching missing number in large data.
>
> Abhishek
>
> (Copy to list)
>
> I don't think anyone has asked WHY you particularly need this to be
> O(logN)? If there are only 32k numbers then the time taken to find the
> missing ones will be pretty small; it will only add up if you are
> doing this search many times, and it becomes a major part of your
> system load.
>
> Or is a question for some other purpose (eg an examination, a job
> interview, a certification)?
>
> I think Chris Taylor's message may be driving at the same point. Mark
> Farnham's answer already gives you the O(N*logN) sorting option...
>
> Regards Nigel
> --
> //www.freelists.org/webpage/oracle-l
>
>
>
--
//www.freelists.org/webpage/oracle-l
Other related posts:
