Re: help with C algorythm (find unique value in an array) could you please make changes

[Ron Johnson <ron.l.johnson@cox.net>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 01/22/07 11:22, Jon Dowland wrote:
> On Mon, Jan 22, 2007 at 10:30:29AM +0000, Jon Dowland wrote:
[snip]
>     /* populate the unique list */
>     for(i = 1; i < argc; ++i) {
>         int val = atoi(argv[i]);
>         if(!in_list(val, list)) {
>             list = add_to_list(val, list);
>         }
>     }

Unless I'm misreading, this would not scale well *at all*.

Instead of using a singly linked list, I'd use a binary tree, where
each leaf node records not only the unique value, but the number of
repeating instances.  That would need log2(num_unique_entries)
accesses per query or insert, instead of, on average,
num_unique_entries/2 accesses per query or insert.


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFFtPeIS9HxQb37XmcRAisNAKDBPDly2U9ra7JZGgBdWnsDzhUfyACg2OrD
IHDlOBKOE9wRqgXbCVkeX/Y=
=klp7
-----END PGP SIGNATURE-----