Back to Questions
1.4k
views4
comments
Sorted list
f#functional

It would be nice to have a functional data structure implementing O(log(n)) sorted insertion in FSharp.Collections.

We can use ResizeArray in combination with BinarySearch... however...
1) It's not functional :-)
2) Insertion is O(n) [because it's not implemented as a list, but an array]
3) Binary search is O(log(n))
=> so ordered insertion is O(n)

.

I agree w/Gary in general, but you may want to look at this collection of posts if you already haven't:

[link:lepensemoi.free.fr]

By on 3/6/2010 10:53 AM ()

based on the lessons from the python/perl

community, it usually ends up more efficient(for most real world

problems anyway) to build an unsorted list then sort at the end where

the sort function is usually some special routines that is very

efficient.

Well, in this case I need to use it as a priority queue, so sorting at the end is not an option.

I agree w/Gary in general, but you may want to look at this collection of posts if you already haven't:

[link:lepensemoi.free.fr]

Interesting, thanks. I might just implement a simple heap.

By on 3/7/2010 4:15 AM ()

If you don't need to have repeated elements, the built in Set type ought to meet your needs, I think.

By on 3/6/2010 9:21 AM ()

based on the lessons from the python/perl community, it usually ends up more efficient(for most real world problems anyway) to build an unsorted list then sort at the end where the sort function is usually some special routines that is very efficient.

By on 3/6/2010 9:44 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper