Previous Entry Share Next Entry
Explaining Language Design (Part 7: Algorithm Complexity)
anime
he_the_great

In the next portion of the talk Scott goes over library consistency. Certainly D has some that people will come across, but I'll continue with the examples given by Scott. I also tend to be blind to most of the inconsistencies.

dlang
void main() {
    int[] v;
    import std.algorithm : sort;
    sort(v); // O(n lg n)

    import std.container : DList;
    DList!int li;
    version(none) sort(li);
    // Error, not random access

In the very beginning D starts out the same as C++. A random access container is sorted in O(n lg n) and a list isn't random access preventing the ability to sort. This keeps sort a constant complexity.

dlang
    sort(v).contains(10); // O(lg n)

Utilizing sort in D provides a thin wrapper around the container. It provides a function 'contains' which will do a binary search for an item and tells you if it was found. Since a list can't be sorted there is no binary search.

dlang
    import std.algorithm : canFind;
    li[].canFind(10); // O(n)
    sort(v).canFind(10); // O(n)
}

As there is no binary search on a list there is another function call 'canFind' found in std.algorithm which will do a O(n) romp to locate a requested element. We can still sort your array and call canFind, which will still be O(n).

Scott goes into some naming items for deleting elements from a container and stable sort. I'm not going into detail here, but as it stands std.container is very detailed about naming and complexity. These obviously are not enforceable, but give direction if a container needs to be created. The module is also very sparse when it comes to actual container implementations.

Conclusion

I think D is in a fairly good position. There are some issues with where to find things. While searching and sorting is found in std.algorithm binary search is actually in std.range.SortedRange (luckily that is mentioned in the sort docs. There is also std.range.assumeSorted if sorting has already been done. Part of the reason useful functions are scattered throughout the different modules is because the modules are generic.

I also think that binary search is a little out of place, I'd expect some generic search function which will operate with the best complexity possible, then have binarySearch and linearSearch; the binarySearch could only operate on a SortedRange. I wouldn't mind if the names were still contains and canFind, just think that placing contains on SortedRange is odd. Specifically I'd love to see a binaryFind which provides the same functionality as std.algorithm.find with binary search.

  1. Part 1: Default Initialization
  2. Part 2: Const Inference
  3. Part 3: Lambdas in C++
  4. Part 4: Lambdas in D
  5. Part 5: Type Inference
  6. Part 6: Inheritance
  7. Part 7: Algorithm Complexity
  8. Part 8: Essential Complexity

?

Log in