Re: [BLACKBOX] AVL Trees

From: [at]} <Bob>
Date: Wed, 7 Sep 2011 19:17:49 +0100

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

> then count the list.
...
> I then traverse the ordered list counting distinct entries.

Why do you need a second pass to count them? You should just add 1 when
you've put a new entry in the list.

Bob

> -----Original Message-----
> From: BlackBox [mailto:BLACKBOX{([at]})nowhere.xy
> Robert (SELEX GALILEO, UK)
> Sent: 07 September 2011 09:27
> To: BLACKBOX{([at]})nowhere.xy
> Subject: Re: [BLACKBOX] AVL Trees
>
> >> 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

----
To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy----boundary-LibPST-iamunique-391380553_-_-
Content-type: application/rtf
Content-transfer-encoding: base64
Content-Disposition: attachment; filename="rtf-body.rtf"
e1xydGYxXGFuc2lcYW5zaWNwZzEyNTJcZnJvbXRleHQgXGRlZmYwe1xmb250dGJsDQp7XGYwXGZz
d2lzc1xmY2hhcnNldDAgQXJpYWw7fQ0Ke1xmMVxmbW9kZXJuIENvdXJpZXIgTmV3O30NCntcZjJc
Zm5pbFxmY2hhcnNldDIgU3ltYm9sO30NCntcZjNcZm1vZGVyblxmY2hhcnNldDAgQ291cmllciBO
ZXc7fX0NCntcY29sb3J0YmxccmVkMFxncmVlbjBcYmx1ZTA7XHJlZDBcZ3JlZW4wXGJsdWUyNTU7
fQ0KXHVjMVxwYXJkXHBsYWluXGRlZnRhYjM2MCBcZjBcZnMyMCA+IHRoZW4gY291bnQgdGhlIGxp
c3QuIFxwYXINCi4uLlxwYXINCj4gSSB0aGVuIHRyYXZlcnNlIHRoZSBvcmRlcmVkIGxpc3QgY291
bnRpbmcgZGlzdGluY3QgZW50cmllcy5ccGFyDQpccGFyDQpXaHkgZG8geW91IG5lZWQgYSBzZWNv
bmQgcGFzcyB0byBjb3VudCB0aGVtPyBZb3Ugc2hvdWxkIGp1c3QgYWRkIDEgd2hlblxwYXINCnlv
dSd2ZSBwdXQgYSBuZXcgZW50cnkgaW4gdGhlIGxpc3QuXHBhcg0KXHBhcg0KQm9iXHBhcg0KXHBh
cg0KPiAtLS0tLU9yaWdpbmFsIE1lc3NhZ2UtLS0tLVxwYXINCj4gRnJvbTogQmxhY2tCb3ggW21h
aWx0bzpCTEFDS0JPWEBMSVNUUy5PQkVST04uQ0hdIE9uIEJlaGFsZiBPZiBDYW1wYmVsbCxccGFy
DQo+IFJvYmVydCAoU0VMRVggR0FMSUxFTywgVUspXHBhcg0KPiBTZW50OiAwNyBTZXB0ZW1iZXIg
MjAxMSAwOToyN1xwYXINCj4gVG86IEJMQUNLQk9YQExJU1RTLk9CRVJPTi5DSFxwYXINCj4gU3Vi
amVjdDogUmU6IFtCTEFDS0JPWF0gQVZMIFRyZWVzXHBhcg0KPiBccGFyDQo+ID4+IEhlbGxvIFJv
YmVydCxccGFyDQo+ID4+XHBhcg0KPiA+PiBXaGF0IGRvIHlvdSBjYWxsIGEgZmFzdCBsaXN0P1xw
YXINCj4gPj5ccGFyDQo+ID4+IEdcJ2U5cmFyZFxwYXINCj4gXHBhcg0KPiBccGFyDQo+IFRoZSBw
cm9ibGVtIGdlbmVyYXRlcyAnQicgbnVtYmVycyBpbiBhIHNvbWUgb3JkZXIgSSBzaGFsbCBjYWxs
XHBhcg0KPiAnUmFuZG9tJywgc2luY2UgSVxwYXINCj4gY2FuJ3QgZXhwbG9pdCBpdC5ccGFyDQo+
IFxwYXINCj4gSSB3YW50IHRvIGNvdW50IHRoZSBudW1iZXIgb2YgZGlzdGluY3QgbnVtYmVycyAn
QScuXHBhcg0KPiBccGFyDQo+IFxwYXINCj4gTXkgJ1Nsb3cgbGlzdC1iYXNlZCBhbGdvcml0aG0n
IGlzIHRvIGFkZCBlYWNoIG51bWJlciB0byB0aGUgbGlzdFxwYXINCj4gbWFpbnRhaW5pbmcgb3Jk
ZXJccGFyDQo+IGFuZCByZWplY3RpbmcgZHVwbGljYXRlcywgdGhlbiBjb3VudCB0aGUgbGlzdC4g
VGhpcyByZXF1aXJlcyBvZiBvcmRlciBCXHBhcg0KPiAqIEEgY29tcGFyaXNvbnMsXHBhcg0KPiBi
dXQgdGhlIGxpc3QgbGVuZ3RoIGlzIG5vIG1vcmUgdGhhbiBBLlxwYXINCj4gXHBhcg0KPiBNeSAn
RmFzdCBsaXN0LWJhc2VkIGFsZ29yaXRobScgaXMgdG8gYWRkIGFsbCB0aGUgbnVtYmVycyB0byB0
aGUgbGlzdCBpblxwYXINCj4gb3JkZXIgb2YgYXJyaXZhbCxccGFyDQo+IHRoZW4gc29ydCB0aGUg
bGlzdC4gSSB1c2UgTWVyZ2Ugc29ydCwgd2hpY2ggaXMgaW4gbXkgbGlzdCBsaWJyYXJ5IHNvXHBh
cg0KPiByZXF1aXJlZCBubyBuZXcgY29kaW5nLFxwYXINCj4gYnV0IGFueSBCIExvZyAoQikgc29y
dCwgb3IgUXVpY2tzb3J0LCB3b3VsZCBiZSBmaW5lLlxwYXINCj4gSSB0aGVuIHRyYXZlcnNlIHRo
ZSBvcmRlcmVkIGxpc3QgY291bnRpbmcgZGlzdGluY3QgZW50cmllcy5ccGFyDQo+IFxwYXINCj4g
VGhlIGRvd25zaWRlIGlzIHRoYXQgdGhlIGxpc3QgaGFzIGEgbGVuZ3RoIG9mIEIsIHdoaWNoIG1p
Z2h0IGJlIG11Y2hccGFyDQo+IG1vcmUgdGhhbiBBLlxwYXINCj4gXHBhcg0KPiBccGFyDQo+IFRo
ZSBhY3R1YWwgcHJvYmxlbSBpc1xwYXINCj4gaHR0cDovL3Byb2plY3RldWxlci5uZXQvaW5kZXgu
cGhwP3NlY3Rpb249cHJvYmxlbXMmaWQ9ODdccGFyDQo+IFxwYXINCj4gXHBhcg0KPiBJIGxpa2Ug
TWVyZ2Ugc29ydCAmIEhlYXAgc29ydCBiZWNhdXNlIGFsdGhvdWdoIHRoZXkgYXJlIG5vdCB0aGUg
ZmFzdGVzdFxwYXINCj4gb24gYXZlcmFnZSwgdGhleSBib3RoXHBhcg0KPiBoYXZlIGdvb2Qgd29y
c3QgY2FzZSBwZXJmb3JtYW5jZS4gSSBmaW5kIE1lcmdlIHNvcnQgY29udmVuaWVudCBmb3JccGFy
DQo+IGxpc3RzLCBIZWFwIHNvcnQgY29udmVuaWVudCBmb3JccGFyDQo+IGFycmF5cy5ccGFyDQo+
IFxwYXINCj4gXHBhcg0KPiBSZWdhcmRzXHBhcg0KPiBccGFyDQo+IFJvYmVydFxwYXINCj4gXHBh
cg0KPiBccGFyDQo+IFNFTEVYIEdhbGlsZW8gTHRkXHBhcg0KPiBSZWdpc3RlcmVkIE9mZmljZTog
U2lnbWEgSG91c2UsIENocmlzdG9waGVyIE1hcnRpbiBSb2FkLCBCYXNpbGRvbixccGFyDQo+IEVz
c2V4IFNTMTQgM0VMXHBhcg0KPiBBIGNvbXBhbnkgcmVnaXN0ZXJlZCBpbiBFbmdsYW5kICYgV2Fs
ZXMuICBDb21wYW55IG5vLiAwMjQyNjEzMlxwYXINCj4gKioqKioqKioqKioqKioqKioqKioqKioq
KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKipccGFyDQo+IFRoaXMg
ZW1haWwgYW5kIGFueSBhdHRhY2htZW50cyBhcmUgY29uZmlkZW50aWFsIHRvIHRoZSBpbnRlbmRl
ZFxwYXINCj4gcmVjaXBpZW50IGFuZCBtYXkgYWxzbyBiZSBwcml2aWxlZ2VkLiBJZiB5b3UgYXJl
IG5vdCB0aGUgaW50ZW5kZWRccGFyDQo+IHJlY2lwaWVudCBwbGVhc2UgZGVsZXRlIGl0IGZyb20g
eW91ciBzeXN0ZW0gYW5kIG5vdGlmeSB0aGUgc2VuZGVyLlxwYXINCj4gWW91IHNob3VsZCBub3Qg
Y29weSBpdCBvciB1c2UgaXQgZm9yIGFueSBwdXJwb3NlIG5vciBkaXNjbG9zZSBvclxwYXINCj4g
ZGlzdHJpYnV0ZSBpdHMgY29udGVudHMgdG8gYW55IG90aGVyIHBlcnNvbi5ccGFyDQo+ICoqKioq
KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioq
KioqKioqXHBhcg0KPiBccGFyDQo+IFxwYXINCj4gLS0tLVxwYXINCj4gVG8gdW5zdWJzY3JpYmUs
IHNlbmQgYSBtZXNzYWdlIHdpdGggYm9keSAiU0lHTk9GRiBCTEFDS0JPWCIgdG9ccGFyDQo+IExJ
U1RTRVJWQExJU1RTLk9CRVJPTi5DSFxwYXINClxwYXINClxwYXINCi0tLS1ccGFyDQpUbyB1bnN1
YnNjcmliZSwgc2VuZCBhIG1lc3NhZ2Ugd2l0aCBib2R5ICJTSUdOT0ZGIEJMQUNLQk9YIiB0byBM
SVNUU0VSVkBMSVNUUy5PfX0AMjXiMgNDdGV4BUEB
----boundary-LibPST-iamunique-391380553_-_---

Received on Wed Sep 07 2011 - 20:17:49 UTC