Re: [BLACKBOX] AVL Trees

From: Campbell, Robert (SELEX GALILEO, UK) <robert.d.campbell{([at]})nowhere.xy>
Date: Wed, 7 Sep 2011 09:26:34 +0100

----boundary-LibPST-iamunique-1875989888_-_-
Content-type: text/plain

>> Hello Robert,
>>
>> What do you call a fast list?
>>
>> Gérard


The problem generates 'B' numbers in a some order I shall call 'Random', since I
can't exploit it.

I want to count the number of distinct numbers 'A'.


My 'Slow list-based algorithm' is to add each number to the list maintaining order
and rejecting duplicates, then count the list. This requires of order B * A comparisons,
but the list length is no more than A.

My 'Fast list-based algorithm' is to add all the numbers to the list in order of arrival,
then sort the list. I use Merge sort, which is in my list library so required no new coding,
but any B Log (B) sort, or Quicksort, would be fine.
I then traverse the ordered list counting distinct entries.

The downside is that the list has a length of B, which might be much more than A.


The actual problem is
http://projecteuler.net/index.php?section=problems&id‡


I like Merge sort & Heap sort because although they are not the fastest on average, they both
have good worst case performance. I find Merge sort convenient for lists, Heap sort convenient for
arrays.


Regards

Robert


SELEX Galileo Ltd
Registered Office: Sigma House, Christopher Martin Road, Basildon, Essex SS14 3EL
A company registered in England & Wales. Company no. 02426132
********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

----
To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy----boundary-LibPST-iamunique-1875989888_-_-
Content-type: application/rtf
Content-transfer-encoding: base64
Content-Disposition: attachment; filename="rtf-body.rtf"
e1xydGYxXGFuc2lcYW5zaWNwZzEyNTJcZnJvbXRleHQgXGRlZmYwe1xmb250dGJsDQp7XGYwXGZz
d2lzc1xmY2hhcnNldDAgQXJpYWw7fQ0Ke1xmMVxmbW9kZXJuIENvdXJpZXIgTmV3O30NCntcZjJc
Zm5pbFxmY2hhcnNldDIgU3ltYm9sO30NCntcZjNcZm1vZGVyblxmY2hhcnNldDAgQ291cmllciBO
ZXc7fX0NCntcY29sb3J0YmxccmVkMFxncmVlbjBcYmx1ZTA7XHJlZDBcZ3JlZW4wXGJsdWUyNTU7
fQ0KXHVjMVxwYXJkXHBsYWluXGRlZnRhYjM2MCBcZjBcZnMyMCA+PiBIZWxsbyBSb2JlcnQsXHBh
cg0KPj4gXHBhcg0KPj4gV2hhdCBkbyB5b3UgY2FsbCBhIGZhc3QgbGlzdD9ccGFyDQo+PiBccGFy
DQo+PiBHXCdlOXJhcmRccGFyDQpccGFyDQpccGFyDQpUaGUgcHJvYmxlbSBnZW5lcmF0ZXMgJ0In
IG51bWJlcnMgaW4gYSBzb21lIG9yZGVyIEkgc2hhbGwgY2FsbCAnUmFuZG9tJywgc2luY2UgSVxw
YXINCmNhbid0IGV4cGxvaXQgaXQuXHBhcg0KXHBhcg0KSSB3YW50IHRvIGNvdW50IHRoZSBudW1i
ZXIgb2YgZGlzdGluY3QgbnVtYmVycyAnQScuXHBhcg0KXHBhcg0KXHBhcg0KTXkgJ1Nsb3cgbGlz
dC1iYXNlZCBhbGdvcml0aG0nIGlzIHRvIGFkZCBlYWNoIG51bWJlciB0byB0aGUgbGlzdCBtYWlu
dGFpbmluZyBvcmRlclxwYXINCmFuZCByZWplY3RpbmcgZHVwbGljYXRlcywgdGhlbiBjb3VudCB0
aGUgbGlzdC4gVGhpcyByZXF1aXJlcyBvZiBvcmRlciBCICogQSBjb21wYXJpc29ucyxccGFyDQpi
dXQgdGhlIGxpc3QgbGVuZ3RoIGlzIG5vIG1vcmUgdGhhbiBBLlxwYXINClxwYXINCk15ICdGYXN0
IGxpc3QtYmFzZWQgYWxnb3JpdGhtJyBpcyB0byBhZGQgYWxsIHRoZSBudW1iZXJzIHRvIHRoZSBs
aXN0IGluIG9yZGVyIG9mIGFycml2YWwsXHBhcg0KdGhlbiBzb3J0IHRoZSBsaXN0LiBJIHVzZSBN
ZXJnZSBzb3J0LCB3aGljaCBpcyBpbiBteSBsaXN0IGxpYnJhcnkgc28gcmVxdWlyZWQgbm8gbmV3
IGNvZGluZyxccGFyDQpidXQgYW55IEIgTG9nIChCKSBzb3J0LCBvciBRdWlja3NvcnQsIHdvdWxk
IGJlIGZpbmUuXHBhcg0KSSB0aGVuIHRyYXZlcnNlIHRoZSBvcmRlcmVkIGxpc3QgY291bnRpbmcg
ZGlzdGluY3QgZW50cmllcy5ccGFyDQpccGFyDQpUaGUgZG93bnNpZGUgaXMgdGhhdCB0aGUgbGlz
dCBoYXMgYSBsZW5ndGggb2YgQiwgd2hpY2ggbWlnaHQgYmUgbXVjaCBtb3JlIHRoYW4gQS5ccGFy
DQpccGFyDQpccGFyDQpUaGUgYWN0dWFsIHByb2JsZW0gaXNccGFyDQpodHRwOi8vcHJvamVjdGV1
bGVyLm5ldC9pbmRleC5waHA/c2VjdGlvbj1wcm9ibGVtcyZpZD04N1xwYXINClxwYXINClxwYXIN
CkkgbGlrZSBNZXJnZSBzb3J0ICYgSGVhcCBzb3J0IGJlY2F1c2UgYWx0aG91Z2ggdGhleSBhcmUg
bm90IHRoZSBmYXN0ZXN0IG9uIGF2ZXJhZ2UsIHRoZXkgYm90aFxwYXINCmhhdmUgZ29vZCB3b3Jz
dCBjYXNlIHBlcmZvcm1hbmNlLiBJIGZpbmQgTWVyZ2Ugc29ydCBjb252ZW5pZW50IGZvciBsaXN0
cywgSGVhcCBzb3J0IGNvbnZlbmllbnQgZm9yXHBhcg0KYXJyYXlzLlxwYXINClxwYXINClxwYXIN
ClJlZ2FyZHNccGFyDQpccGFyDQpSb2JlcnRccGFyDQpccGFyDQpccGFyDQpTRUxFWCBHYWxpbGVv
IEx0ZFxwYXINClJlZ2lzdGVyZWQgT2ZmaWNlOiBTaWdtYSBIb3VzZSwgQ2hyaXN0b3BoZXIgTWFy
dGluIFJvYWQsIEJhc2lsZG9uLCBFc3NleCBTUzE0IDNFTFxwYXINCkEgY29tcGFueSByZWdpc3Rl
cmVkIGluIEVuZ2xhbmQgJiBXYWxlcy4gIENvbXBhbnkgbm8uIDAyNDI2MTMyXHBhcg0KKioqKioq
KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioq
KioqKipccGFyDQpUaGlzIGVtYWlsIGFuZCBhbnkgYXR0YWNobWVudHMgYXJlIGNvbmZpZGVudGlh
bCB0byB0aGUgaW50ZW5kZWRccGFyDQpyZWNpcGllbnQgYW5kIG1heSBhbHNvIGJlIHByaXZpbGVn
ZWQuIElmIHlvdSBhcmUgbm90IHRoZSBpbnRlbmRlZFxwYXINCnJlY2lwaWVudCBwbGVhc2UgZGVs
ZXRlIGl0IGZyb20geW91ciBzeXN0ZW0gYW5kIG5vdGlmeSB0aGUgc2VuZGVyLlxwYXINCllvdSBz
aG91bGQgbm90IGNvcHkgaXQgb3IgdXNlIGl0IGZvciBhbnkgcHVycG9zZSBub3IgZGlzY2xvc2Ug
b3JccGFyDQpkaXN0cmlidXRlIGl0cyBjb250ZW50cyB0byBhbnkgb3RoZXIgcGVyc29uLlxwYXIN
CioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioq
KioqKioqKioqKioqXHBhcg0KXHBhcg0KXHBhcg0KLS0tLVxwYXINClRvIHVuc3Vic2NyaWJlLCBz
ZW5kIGEgbWVzc2FnZSB3aXRoIGJvZHkgIlNJR05PRkYgQkxBQ0tCT1giIHRvIExJU1RTRVJWQExJ
U1RTLk9CRVJPTi5DSH19AHZhdC0
----boundary-LibPST-iamunique-1875989888_-_---

Received on Wed Sep 07 2011 - 10:26:34 UTC