www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Complexity nomenclature

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Consider the collections universe. So we have an imperative primitive like:

c.insertAfter(r, x)

where c is a collection, r is a range previously extracted from c, and x 
is a value convertible to collection's element type. The expression 
imperatively inserts x in the collection right after r.

Now this primitive may have three complexities:

* linear in the length of r (e.g. c is a singly-linked list)

* linear in the number of elements after r in the collection (e.g. c is 
an array)

* constant (c is a doubly-linked list)

These complexities must be reflected in the name of the primitives. Or 
perhaps it's okay to conflate a couple of them. I know names are 
something we're awfully good at discussing :o). Destroy!


Andrei
Dec 03 2015
next sibling parent reply Jack Stouffer <jack jackstouffer.com> writes:
On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu 
wrote:
 These complexities must be reflected in the name of the 
 primitives.
I don't see why. IMO, names should convey what the function does, not how it does it. Complexity is usually put in the function documentation in Phobos when it's not constant, especially for range based ones, I don't see a reason to change that.
Dec 03 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 08:37 PM, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
 These complexities must be reflected in the name of the primitives.
I don't see why. IMO, names should convey what the function does, not how it does it. Complexity is usually put in the function documentation in Phobos when it's not constant, especially for range based ones, I don't see a reason to change that.
Complexity is part of the semantics, and in my design names and their semantics go hand in hand. -- Andrei
Dec 03 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 03:18 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 08:37 PM, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
 These complexities must be reflected in the name of the primitives.
I don't see why. IMO, names should convey what the function does, not how it does it. Complexity is usually put in the function documentation in Phobos when it's not constant, especially for range based ones, I don't see a reason to change that.
Complexity is part of the semantics, and in my design names and their semantics go hand in hand. -- Andrei
Which is sensible. But in any given context, some parts of the semantics are usually abstracted away. Sometimes one wants to abstract over running times of called methods. ("This function calls this other function at most O(n) times.")
Dec 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 09:24 PM, Timon Gehr wrote:
 On 12/04/2015 03:18 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 08:37 PM, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
 These complexities must be reflected in the name of the primitives.
I don't see why. IMO, names should convey what the function does, not how it does it. Complexity is usually put in the function documentation in Phobos when it's not constant, especially for range based ones, I don't see a reason to change that.
Complexity is part of the semantics, and in my design names and their semantics go hand in hand. -- Andrei
Which is sensible. But in any given context, some parts of the semantics are usually abstracted away. Sometimes one wants to abstract over running times of called methods. ("This function calls this other function at most O(n) times.")
Sure, and there will be provision for that. The collections framework will contain logic such as: "If collection type C implements insertAfter, then implement UFCS function linearInsertAfter that forwards to it". So if as user you're fine with linearInsertAfter, it'll work as an upper bound. -- Andrei
Dec 03 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 03:35 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 09:24 PM, Timon Gehr wrote:
 On 12/04/2015 03:18 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 08:37 PM, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
 These complexities must be reflected in the name of the primitives.
I don't see why. IMO, names should convey what the function does, not how it does it. Complexity is usually put in the function documentation in Phobos when it's not constant, especially for range based ones, I don't see a reason to change that.
Complexity is part of the semantics, and in my design names and their semantics go hand in hand. -- Andrei
Which is sensible. But in any given context, some parts of the semantics are usually abstracted away. Sometimes one wants to abstract over running times of called methods. ("This function calls this other function at most O(n) times.")
Sure, and there will be provision for that. The collections framework will contain logic such as: "If collection type C implements insertAfter, then implement UFCS function linearInsertAfter that forwards to it". So if as user you're fine with linearInsertAfter, it'll work as an upper bound. -- Andrei
This only works if the module imports std.container. Also, I might be okay with arbitrary running times, even super-linear. There's also the case where I want to implement a wrapper around a generic container. I will then need to provide static introspection in order to expose the methods with the correct names.
Dec 03 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 09:52 PM, Timon Gehr wrote:
 This only works if the module imports std.container.
Yeah, that's the way it works.
 Also, I might be
 okay with arbitrary running times, even super-linear.
Hmmmm... right, no provision for that right now. Need to think about it. Maybe put them all in a "superlinear" bin. Names are hard.
 There's also the
 case where I want to implement a wrapper around a generic container. I
 will then need to provide static introspection in order to expose the
 methods with the correct names.
Yep, again that's the way it's done. Andrei
Dec 03 2015
prev sibling parent reply Andrea Fontana <nospam example.com> writes:
On Friday, 4 December 2015 at 01:37:33 UTC, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu 
 wrote:
 These complexities must be reflected in the name of the 
 primitives.
I don't see why. IMO, names should convey what the function does, not how it does it.
I'm agree. It sounds like a bad idea. And who knows, maybe someone will discover a more efficient way to implement "insertAfter" or the collection itself... We should change its name?
Dec 04 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 04:27 AM, Andrea Fontana wrote:
 And who knows, maybe someone will discover a more efficient way to
 implement "insertAfter" or the collection itself... We should change its
 name?
Of course. The old name will still work because, remember, there's a hierarchy of operations; those that promise less automatically forward to those that promise more. -- Andrei
Dec 04 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 02:27 AM, Andrei Alexandrescu wrote:
 Consider the collections universe. So we have an imperative primitive like:

 c.insertAfter(r, x)

 where c is a collection, r is a range previously extracted from c, and x
 is a value convertible to collection's element type. The expression
 imperatively inserts x in the collection right after r.

 Now this primitive may have three complexities:

 * linear in the length of r (e.g. c is a singly-linked list)

 * linear in the number of elements after r in the collection (e.g. c is
 an array)

 * constant (c is a doubly-linked list)

 These complexities must be reflected in the name of the primitives. Or
 perhaps it's okay to conflate a couple of them. I know names are
 something we're awfully good at discussing :o). Destroy!


 Andrei
Regarding nomenclature, it would be awesome if we could call this "running time" instead of "complexity". Algorithms have running times and memory usages. Problems have (time and space) complexities. I know that calling running time 'complexity' is awfully popular outside of actual complexity theory papers. I don't really understand what calling it 'complexity' actually buys though.
Dec 03 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 08:55 PM, Timon Gehr wrote:
 I don't really understand what calling it 'complexity' actually buys
 though.
Instant understanding by everyone. -- Andrei
Dec 03 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 03:19 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 08:55 PM, Timon Gehr wrote:
 I don't really understand what calling it 'complexity' actually buys
 though.
Instant understanding by everyone. -- Andrei
Well, no. "running time" is actually more descriptive.
Dec 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 09:27 PM, Timon Gehr wrote:
 On 12/04/2015 03:19 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 08:55 PM, Timon Gehr wrote:
 I don't really understand what calling it 'complexity' actually buys
 though.
Instant understanding by everyone. -- Andrei
Well, no. "running time" is actually more descriptive.
http://en.cppreference.com/w/cpp/container/forward_list/insert_after Andrei
Dec 03 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 03:36 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 09:27 PM, Timon Gehr wrote:
 On 12/04/2015 03:19 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 08:55 PM, Timon Gehr wrote:
 I don't really understand what calling it 'complexity' actually buys
 though.
Instant understanding by everyone. -- Andrei
Well, no. "running time" is actually more descriptive.
http://en.cppreference.com/w/cpp/container/forward_list/insert_after Andrei
Yes, I know it is popular.
Dec 03 2015
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 03:36 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 09:27 PM, Timon Gehr wrote:
 On 12/04/2015 03:19 AM, Andrei Alexandrescu wrote:
 On 12/03/2015 08:55 PM, Timon Gehr wrote:
 I don't really understand what calling it 'complexity' actually buys
 though.
Instant understanding by everyone. -- Andrei
Well, no. "running time" is actually more descriptive.
http://en.cppreference.com/w/cpp/container/forward_list/insert_after Andrei
http://www.merriam-webster.com/dictionary/literally
Dec 03 2015
prev sibling next sibling parent reply Xinok <xinok live.com> writes:
On Friday, 4 December 2015 at 01:55:15 UTC, Timon Gehr wrote:
 Regarding nomenclature, it would be awesome if we could call 
 this "running time" instead of "complexity". Algorithms have 
 running times and memory usages. Problems have (time and space) 
 complexities. I know that calling running time 'complexity' is 
 awfully popular outside of actual complexity theory papers. I 
 don't really understand what calling it 'complexity' actually 
 buys though.
I've seen you mention this before, and while you may be correct, the term "complexity" is so widely applied to algorithms that it's not worth going against the norm. For the vast majority of computer scientists, when they hear the term "time complexity", they immediately understand it as running time. In fact, what I've seen most often is that algorithms have complexities and problems fall into a *complexity class*. For example, just take a look at the Wikipedia page on time complexity: https://en.wikipedia.org/wiki/Time_complexity
Dec 03 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 03:34 AM, Xinok wrote:
 On Friday, 4 December 2015 at 01:55:15 UTC, Timon Gehr wrote:
 Regarding nomenclature, it would be awesome if we could call this
 "running time" instead of "complexity". Algorithms have running times
 and memory usages. Problems have (time and space) complexities. I know
 that calling running time 'complexity' is awfully popular outside of
 actual complexity theory papers. I don't really understand what
 calling it 'complexity' actually buys though.
I've seen you mention this before, and while you may be correct, the term "complexity" is so widely applied to algorithms that it's not worth going against the norm. For the vast majority of computer scientists, when they hear the term "time complexity", they immediately understand it as running time.
I understand what is meant, but it is painful, much like when somebody uses "literally" but actually means "figuratively". :-)
 In fact, what I've seen most often is that
 algorithms have complexities and problems fall into a *complexity
 class*. For example, just take a look at the Wikipedia page on time
 complexity:

 https://en.wikipedia.org/wiki/Time_complexity
It's a schizophrenic article. It mostly uses the standard terminology starting from this section: https://en.wikipedia.org/wiki/Time_complexity#Constant_time I guess the article has multiple authors, only some of which are complexity theorists.
Dec 03 2015
prev sibling parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Friday, 4 December 2015 at 01:55:15 UTC, Timon Gehr wrote:
 awfully popular outside of actual complexity theory papers. I 
 don't really understand what calling it 'complexity' actually 
 buys though.
It will make static arrays look very good. All operations are O(1).
Dec 04 2015
prev sibling next sibling parent reply Idan Arye <GenericNPC gmail.com> writes:
On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu 
wrote:
 Consider the collections universe. So we have an imperative 
 primitive like:

 c.insertAfter(r, x)

 where c is a collection, r is a range previously extracted from 
 c, and x is a value convertible to collection's element type. 
 The expression imperatively inserts x in the collection right 
 after r.

 Now this primitive may have three complexities:

 * linear in the length of r (e.g. c is a singly-linked list)

 * linear in the number of elements after r in the collection 
 (e.g. c is an array)

 * constant (c is a doubly-linked list)

 These complexities must be reflected in the name of the 
 primitives. Or perhaps it's okay to conflate a couple of them. 
 I know names are something we're awfully good at discussing 
 :o). Destroy!


 Andrei
The complexities of the operations is a property of the data structure being used. If each collection type will have it's own set of method names based on the complexity of operations on it, we won't be able to have templated functions that operate on any kind of collection(or at the very least, these functions will be really tedious to code).
Dec 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 09:10 PM, Idan Arye wrote:
 The complexities of the operations is a property of the data structure
 being used. If each collection type will have it's own set of method
 names based on the complexity of operations on it, we won't be able to
 have templated functions that operate on any kind of collection(or at
 the very least, these functions will be really tedious to code).
Your premise is right but you reach the negation of the correct conclusion. -- Andrei
Dec 03 2015
parent reply Jack Stouffer <jack jackstouffer.com> writes:
On Friday, 4 December 2015 at 02:21:12 UTC, Andrei Alexandrescu 
wrote:
 On 12/03/2015 09:10 PM, Idan Arye wrote:
 The complexities of the operations is a property of the data 
 structure
 being used. If each collection type will have it's own set of 
 method
 names based on the complexity of operations on it, we won't be 
 able to
 have templated functions that operate on any kind of 
 collection(or at
 the very least, these functions will be really tedious to 
 code).
Your premise is right but you reach the negation of the correct conclusion. -- Andrei
How so? If a singly linked list and a doubly linked list have two different method names for the same operation, then they cannot be easily templated.
Dec 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/3/15 10:29 PM, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 02:21:12 UTC, Andrei Alexandrescu wrote:
 On 12/03/2015 09:10 PM, Idan Arye wrote:
 The complexities of the operations is a property of the data structure
 being used. If each collection type will have it's own set of method
 names based on the complexity of operations on it, we won't be able to
 have templated functions that operate on any kind of collection(or at
 the very least, these functions will be really tedious to code).
Your premise is right but you reach the negation of the correct conclusion. -- Andrei
How so? If a singly linked list and a doubly linked list have two different method names for the same operation, then they cannot be easily templated.
Took me a while to figure. There's a hierarchy of operations, e.g. if a collection implements insert, it automatically implements linearInsert. And so on. The collections framework provides these defaults, so client code that needs quick insert uses insert, whereas code that's fine with a linear upper bound uses linearInsert and captures both. Another way to look at it: in STL container-independent code is near impossible because different containers use the same signature for operations that are different (either wrt iterator invalidation or complexity). My design avoids that by giving distinct operations distinct names. Andrei
Dec 03 2015
next sibling parent reply Tofu Ninja <emmons0 purdue.edu> writes:
On Friday, 4 December 2015 at 03:37:10 UTC, Andrei Alexandrescu 
wrote:
 On 12/3/15 10:29 PM, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 02:21:12 UTC, Andrei 
 Alexandrescu wrote:
 On 12/03/2015 09:10 PM, Idan Arye wrote:
 The complexities of the operations is a property of the data 
 structure
 being used. If each collection type will have it's own set 
 of method
 names based on the complexity of operations on it, we won't 
 be able to
 have templated functions that operate on any kind of 
 collection(or at
 the very least, these functions will be really tedious to 
 code).
Your premise is right but you reach the negation of the correct conclusion. -- Andrei
How so? If a singly linked list and a doubly linked list have two different method names for the same operation, then they cannot be easily templated.
Took me a while to figure. There's a hierarchy of operations, e.g. if a collection implements insert, it automatically implements linearInsert. And so on. The collections framework provides these defaults, so client code that needs quick insert uses insert, whereas code that's fine with a linear upper bound uses linearInsert and captures both. Another way to look at it: in STL container-independent code is near impossible because different containers use the same signature for operations that are different (either wrt iterator invalidation or complexity). My design avoids that by giving distinct operations distinct names. Andrei
This sounds really complicated to use? What are the benefits? When would a generic algorithm even need to know the complexity of the container? Also maybe a simpler idea would just be to annotate the the operations with there complexity with UDAs. That way things that really care about the complexity can get it, and those who don't can ignore it. It has the benefit of being self documenting as well.
Dec 03 2015
next sibling parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Friday, 4 December 2015 at 06:05:55 UTC, Tofu Ninja wrote:
 Also maybe a simpler idea would just be to annotate the the 
 operations with there complexity with UDAs. That way things 
 that really care about the complexity can get it, and those who 
 don't can ignore it. It has the benefit of being self 
 documenting as well.
Yes, but can you export it reliably in generically composed functions? Say you have a loop of N iterations calling a function that involves M operations, you want to export N*M, but then the caller needs to know what N and M are referring to, so you need some standard way of getting there. (e.g. N could be number of edges and M could be number of nodes or something).
Dec 04 2015
prev sibling next sibling parent reply Jakob Ovrum <jakobovrum gmail.com> writes:
On Friday, 4 December 2015 at 06:05:55 UTC, Tofu Ninja wrote:
 When would a generic algorithm even need to know the complexity 
 of the container?
A generic algorithm that uses exponential time when given the "wrong" inputs is a hidden danger. This can easily happen when composing with linear algorithms. This naming scheme, also employed by std.container, prevents this.
 Also maybe a simpler idea would just be to annotate the the 
 operations with there complexity with UDAs. That way things 
 that really care about the complexity can get it, and those who 
 don't can ignore it. It has the benefit of being self 
 documenting as well.
If you don't care about the complexity, why are you using collections? Just use T[] and T[U]. Surely choosing a data structure is all about complexity (barring some details like optimizing for cache locality or small data structures).
Dec 04 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 03:41 AM, Jakob Ovrum wrote:
 On Friday, 4 December 2015 at 06:05:55 UTC, Tofu Ninja wrote:
 When would a generic algorithm even need to know the complexity of the
 container?
A generic algorithm that uses exponential time when given the "wrong" inputs is a hidden danger. This can easily happen when composing with linear algorithms. This naming scheme, also employed by std.container, prevents this.
 Also maybe a simpler idea would just be to annotate the the operations
 with there complexity with UDAs. That way things that really care
 about the complexity can get it, and those who don't can ignore it. It
 has the benefit of being self documenting as well.
If you don't care about the complexity, why are you using collections? Just use T[] and T[U]. Surely choosing a data structure is all about complexity (barring some details like optimizing for cache locality or small data structures).
WORD! -- Andrei
Dec 04 2015
prev sibling next sibling parent ZombineDev <valid_email he.re> writes:
On Friday, 4 December 2015 at 06:05:55 UTC, Tofu Ninja wrote:
 On Friday, 4 December 2015 at 03:37:10 UTC, Andrei Alexandrescu 
 wrote:
 On 12/3/15 10:29 PM, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 02:21:12 UTC, Andrei 
 Alexandrescu wrote:
 On 12/03/2015 09:10 PM, Idan Arye wrote:
 The complexities of the operations is a property of the 
 data structure
 being used. If each collection type will have it's own set 
 of method
 names based on the complexity of operations on it, we won't 
 be able to
 have templated functions that operate on any kind of 
 collection(or at
 the very least, these functions will be really tedious to 
 code).
Your premise is right but you reach the negation of the correct conclusion. -- Andrei
How so? If a singly linked list and a doubly linked list have two different method names for the same operation, then they cannot be easily templated.
Took me a while to figure. There's a hierarchy of operations, e.g. if a collection implements insert, it automatically implements linearInsert. And so on. The collections framework provides these defaults, so client code that needs quick insert uses insert, whereas code that's fine with a linear upper bound uses linearInsert and captures both. Another way to look at it: in STL container-independent code is near impossible because different containers use the same signature for operations that are different (either wrt iterator invalidation or complexity). My design avoids that by giving distinct operations distinct names. Andrei
This sounds really complicated to use? What are the benefits? When would a generic algorithm even need to know the complexity of the container? Also maybe a simpler idea would just be to annotate the the operations with there complexity with UDAs. That way things that really care about the complexity can get it, and those who don't can ignore it. It has the benefit of being self documenting as well.
Ranges are a good example - they provide only the operations thay can efficiently implement. For example forward ranges could provide random access but at the cost of linear running time. std.containers provides the `elem in container` operation only if they can implement it in logarithmic time or faster. The fact that you can't use opIn for DList or Array is very good, because it prevents you from writing inefficient genric code. You're algorithm will manifest that it can only work with containers provide efficient operations and because of that you can be sure what its time complexity would be. You should choose a specific data structure only because you can efficiently implement the algorithm you have in mind with it. One of worst examples of the opposite is .Count extention method in .NET (which happens to have the same name as .Count member function of ICollection - one of the most used (often implicitly) interfaces), which has linear running time. The most horrible thing I have seen!
Dec 04 2015
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 01:05 AM, Tofu Ninja wrote:
 Also maybe a simpler idea would just be to annotate the the operations
 with there complexity with UDAs.
Great idea, will keep it in mind. Thanks! -- Andrei
Dec 04 2015
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, 4 December 2015 at 13:59:41 UTC, Andrei Alexandrescu 
wrote:
 On 12/04/2015 01:05 AM, Tofu Ninja wrote:
 Also maybe a simpler idea would just be to annotate the the 
 operations
 with there complexity with UDAs.
Great idea, will keep it in mind. Thanks! -- Andrei
Yeah. If the primary reason to have stable and linear and whatnot in the names is so that introspection can be used on them, then UDAs will work fine for that. Where it's stickier is if you're just calling them in generic code, since then you have no protection against the complexity changing when the container being used changes. But pretty much no one is going to be wanting to use stuff like stableLinearInsert or stable.linear.insert in their code instead of insert. So, while having the complexity be part of the API has some serious advantages, it's not user-friendly for normal use, whereas the UDAs put you somewhere in between not having the complexity in the API at all and forcing everyone to type out the complexity every time they use a function. - Jonathan M Davis
Dec 04 2015
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 01:05 AM, Tofu Ninja wrote:
 When would a generic algorithm even need to know the complexity of the
 container?
Only always :o). -- Andrei
Dec 04 2015
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 01:05 AM, Tofu Ninja wrote:
 Also maybe a simpler idea would just be to annotate the the operations
 with there complexity with UDAs. That way things that really care about
 the complexity can get it, and those who don't can ignore it. It has the
 benefit of being self documenting as well.
Well look at what the cat dragged in: http://dpaste.dzfl.pl/711aecacc450 That's quite promising. The code is very preliminary and uses strings for typical complexity values (e.g. "constant", "linear", and later "loglinear" etc). I need to see how to integrate this whole idea. Also an unpleasant problem is overloading - when present, user code needs to specify which overload they're referring to. Anyhow, this is really interesting. Thanks Tofu. Andrei
Dec 04 2015
next sibling parent ref2401 <refactor24 gmail.com> writes:
On Friday, 4 December 2015 at 16:06:25 UTC, Andrei Alexandrescu 
wrote:
 Well look at what the cat dragged in:

 http://dpaste.dzfl.pl/711aecacc450

 That's quite promising. The code is very preliminary and uses 
 strings for typical complexity values (e.g. "constant", 
 "linear", and later "loglinear" etc). I need to see how to 
 integrate this whole idea.

 Also an unpleasant problem is overloading - when present, user 
 code needs to specify which overload they're referring to.

 Anyhow, this is really interesting. Thanks Tofu.


 Andrei
Wow! It looks really great.
Dec 04 2015
prev sibling next sibling parent Jack Stouffer <jack jackstouffer.com> writes:
On Friday, 4 December 2015 at 16:06:25 UTC, Andrei Alexandrescu 
wrote:
 Well look at what the cat dragged in:

 http://dpaste.dzfl.pl/711aecacc450
This is a great compromise; I (and everyone else probably) would love to see a prototype of this when it's ready.
Dec 04 2015
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 11:06 AM, Andrei Alexandrescu wrote:
 On 12/04/2015 01:05 AM, Tofu Ninja wrote:
 Also maybe a simpler idea would just be to annotate the the operations
 with there complexity with UDAs. That way things that really care about
 the complexity can get it, and those who don't can ignore it. It has the
 benefit of being self documenting as well.
Well look at what the cat dragged in: http://dpaste.dzfl.pl/711aecacc450
Following up on this, I thought I'd define a little algebra for complexities. It will be closed (no arbitrary expressions) and will support only the usually encountered complexities. The idea is to allow functions to compute their own complexity in terms of complexities of their respective primitives. Here's the algebra. Terms: 1 = O(1) log = O(log n) plog = O((log n)^k) sqrt = O(sqrt n) lin = O(n) linlog = O(n * log n) linplog = O(n * (log n)^k) poly = O(n^k) exp = O(2^n) Ordering: Terms above are in increasing order. Summation: x + y = max(x, y) Product: | 1 log plog sqrt lin linlog poly exp -------+------------------------------------------------------------ 1 | 1 log plog sqrt lin linlog poly exp log | log plog plog ? linlog ? poly exp plog | plog plog plog ? linplog linplog poly exp sqrt | sqrt ? ? lin poly poly poly exp lin | lin linlog linplog poly poly poly poly exp linlog | linlog linplog linplog poly poly poly poly exp poly | poly poly poly poly poly poly poly exp exp | exp exp exp exp exp exp exp exp I've left a few question marks for the tricky cases. Ideas? Andrei
Dec 04 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 01:37 PM, Andrei Alexandrescu wrote:
         | 1       log      plog     sqrt  lin      linlog   poly  exp
 -------+------------------------------------------------------------
 1      | 1       log      plog     sqrt  lin      linlog   poly  exp
 log    | log     plog     plog     ?     linlog   ?        poly  exp
 plog   | plog    plog     plog     ?     linplog  linplog  poly  exp
 sqrt   | sqrt    ?        ?        lin   poly     poly     poly  exp
 lin    | lin     linlog   linplog  poly  poly     poly     poly  exp
 linlog | linlog  linplog  linplog  poly  poly     poly     poly  exp
 poly   | poly    poly     poly     poly  poly     poly     poly  exp
 exp    | exp     exp      exp      exp   exp      exp      exp   exp

 I've left a few question marks for the tricky cases. Ideas?
The question mark at log * linlog is spurious; should be replaced with linplog. So the tricky cases are sqrt * log and sqrt * plog. Andrei
Dec 04 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 07:37 PM, Andrei Alexandrescu wrote:
 Following up on this, I thought I'd define a little algebra ....
 It will be closed (no arbitrary expressions)
 ...
I think that the exponents matter. E.g. n^1.5 vs n^2. The algebra can be made more expressive while simplifying its implementation.
 The idea is to allow functions to compute their own complexity in terms
 of complexities of their respective primitives.

 Here's the algebra.

 Terms:

 1 = O(1)
 log = O(log n)
 plog = O((log n)^k)
 sqrt = O(sqrt n)
 lin = O(n)
 linlog = O(n * log n)
 linplog = O(n * (log n)^k)
 poly = O(n^k)
 exp = O(2^n)
Example alternative: struct BigO{ Fraction logExp; Fraction polyExp; Fraction expBase; bool opCmp(BigO rhs){ return tuple(expBase,polyExp,logExp).opCmp(tuple(rhs.expBase,polyExp,logExp)); } BigO opBinary(string op:"*")(BigO rhs){ return BigO(logExp+rhs.logExp,polyExp+rhs.polyExp,expBase*rhs.expBase); } // ... } Your cases then become: O(1): expBase=1, polyExp=0, logExp=0; O(log n): expBase=1, polyExp=0, logExp=1; O((log n)^k): expBase=1, polyExp=0, logExp=k; O(sqrt n): expBase=1, polyExp=Fraction(1,2), logExp=0; O(n): expBase=1, polyExp=1, logExp=0; O(n * log n): expBase=1, polyExp=1, logExp=1; O(n * (log n)^k): expBase=1, polyExp=1, logExp=k; O(n^k): expBase=1, polyExp=k, logExp=0; O(2^n): expBase=2, polyExp=0, logExp=0; Combinations just work, especially n^(1/2) * log n.
Dec 04 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Timon Gehr <timon.gehr gmx.ch> wrote:
 On 12/04/2015 07:37 PM, Andrei Alexandrescu wrote:
 Following up on this, I thought I'd define a little algebra ....
 It will be closed (no arbitrary expressions)
 ...
I think that the exponents matter. E.g. n^1.5 vs n^2. The algebra can be made more expressive while simplifying its implementation.
 
 The idea is to allow functions to compute their own complexity in terms
 of complexities of their respective primitives.
 
 Here's the algebra.
 
 Terms:
 
 1 = O(1)
 log = O(log n)
 plog = O((log n)^k)
 sqrt = O(sqrt n)
 lin = O(n)
 linlog = O(n * log n)
 linplog = O(n * (log n)^k)
 poly = O(n^k)
 exp = O(2^n)
Example alternative: struct BigO{ Fraction logExp; Fraction polyExp; Fraction expBase; bool opCmp(BigO rhs){ return tuple(expBase,polyExp,logExp).opCmp(tuple(rhs.expBase,polyExp,logExp)); } BigO opBinary(string op:"*")(BigO rhs){ return BigO(logExp+rhs.logExp,polyExp+rhs.polyExp,expBase*rhs.expBase); } // ... } Your cases then become: O(1): expBase=1, polyExp=0, logExp=0; O(log n): expBase=1, polyExp=0, logExp=1; O((log n)^k): expBase=1, polyExp=0, logExp=k; O(sqrt n): expBase=1, polyExp=Fraction(1,2), logExp=0; O(n): expBase=1, polyExp=1, logExp=0; O(n * log n): expBase=1, polyExp=1, logExp=1; O(n * (log n)^k): expBase=1, polyExp=1, logExp=k; O(n^k): expBase=1, polyExp=k, logExp=0; O(2^n): expBase=2, polyExp=0, logExp=0; Combinations just work, especially n^(1/2) * log n.
Nice, I'll continue with this. Thanks! I won't use expBase because no operation leads to it; instead I'll just lump everything superpoly into one "fast growing" category.
Dec 04 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 09:03 PM, Andrei Alexandrescu wrote:
Your cases then become:

O(1):     expBase=1, polyExp=0, logExp=0;
O(log n): expBase=1, polyExp=0, logExp=1;
O((log n)^k): expBase=1, polyExp=0, logExp=k;
O(sqrt n): expBase=1, polyExp=Fraction(1,2), logExp=0;
O(n): expBase=1, polyExp=1, logExp=0;
O(n * log n): expBase=1, polyExp=1, logExp=1;
O(n * (log n)^k): expBase=1, polyExp=1, logExp=k;
O(n^k): expBase=1, polyExp=k, logExp=0;
O(2^n): expBase=2, polyExp=0, logExp=0;

Combinations just work, especially n^(1/2) * log n.
Nice, I'll continue with this. Thanks! I won't use expBase because no operation leads to it; instead I'll just lump everything superpoly into one "fast growing" category.
This is probably sensible in the context of std.container. Note that some containers only give amortized guarantees. E.g. in C++, calling push_back n times on a vector that starts out empty is O(n), but the worst case for a single push_back is Ω(n). Another question is how widely applicable BigO should become beyond std.container. E.g. some runtime bounds have multiple parameters.
Dec 04 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 04:40 PM, Timon Gehr wrote:
 Another question is how widely applicable BigO should become beyond
 std.container.
I'm thinking we could add complexity annotations to range functions. For example the complexity of map is linear etc.
E.g. some runtime bounds have multiple parameters.
Yah, I was wondering how necessary that'd be. One problem is how to align parameters of different algorithms, for example say one is n * m and the other is m log n. What if they swap the order of m and n? I guess some reasonable convention should take care of this. Otherwise, we'll need to use a hashtable mapping names to (exp, logExp) tuples. Andrei
Dec 04 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/04/2015 11:57 PM, Andrei Alexandrescu wrote:
 On 12/04/2015 04:40 PM, Timon Gehr wrote:
 Another question is how widely applicable BigO should become beyond
 std.container.
I'm thinking we could add complexity annotations to range functions. For example the complexity of map is linear etc. ...
It depends on the mapped function.
 E.g. some runtime bounds have multiple parameters.
Yah, I was wondering how necessary that'd be. One problem is how to align parameters of different algorithms, for example say one is n * m and the other is m log n. What if they swap the order of m and n? I guess some reasonable convention should take care of this. Otherwise, we'll need to use a hashtable mapping names to (exp, logExp) tuples. Andrei
If only products should be expressible, this would maybe be reasonable as well: void foo( (BigO.linear) int n, (BigO.linear) int m); But UDAs for parameters are not supported.
Dec 04 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/05/2015 04:24 AM, Timon Gehr wrote:

 If only products should be expressible,
But I think not. O(n+m) is common.
Dec 04 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 10:24 PM, Timon Gehr wrote:
 void foo( (BigO.linear) int n, (BigO.linear) int m);

 But UDAs for parameters are not supported.
That's actually pretty neat and easy to work around like this: void foo(int n, int m) (BigOParam!2(BigO.linear, BigO.linear); In fact I went through the implementation but soon I hit a wall: what's the _relationship_ between the two growths? It may be the sum O(m + n) but also the product O(m * n). So the operator must be encoded as well. Then what do we do with more complex relationships like O((m + n) log n) etc. Then once you get to some reasonable formula, what's the ordering on top of these complexities? Probably difficult. I gave up on this for the time being. Ideas welcome. Andrei
Dec 05 2015
next sibling parent reply BLM768 <blm768 gmail.com> writes:
On Saturday, 5 December 2015 at 20:48:16 UTC, Andrei Alexandrescu 
wrote:
 On 12/04/2015 10:24 PM, Timon Gehr wrote:
 In fact I went through the implementation but soon I hit a 
 wall: what's the _relationship_ between the two growths? It may 
 be the sum O(m + n) but also the product O(m * n). So the 
 operator must be encoded as well.

 Then what do we do with more complex relationships like O((m + 
 n) log n) etc.

 Then once you get to some reasonable formula, what's the 
 ordering on top of these complexities? Probably difficult.

 I gave up on this for the time being. Ideas welcome.

 Andrei
Well, we could see how CAS libraries handle this kind of stuff (if there _is_ one which handles it)... Really, though, with the more complex algorithms, you start running into the kinds of issues noted in the first reply to this article: http://www.perlmonks.org/?node_id=573138 Besides, is anyone actually going to specify that they need an algorithm that is O(log(n) + m^2) or whatever? Or would a function just take _two_ algorithms, assert that each is O(log(n)) and O(m^2), respectively, and then compose them itself? The complexities depend on the types of container anyway, so in general, you should get only multi-term big-O notation when you're using multiple containers (or Cartesian products of a container with itself or something like that). Can't we just make sure one container's insert() and the other container's sort() work within a certain complexity?
Dec 05 2015
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sat, Dec 05, 2015 at 09:52:08PM +0000, BLM768 via Digitalmars-d wrote:
 On Saturday, 5 December 2015 at 20:48:16 UTC, Andrei Alexandrescu wrote:
On 12/04/2015 10:24 PM, Timon Gehr wrote:
In fact I went through the implementation but soon I hit a wall:
what's the _relationship_ between the two growths? It may be the sum
O(m + n) but also the product O(m * n). So the operator must be
encoded as well.

Then what do we do with more complex relationships like O((m + n) log
n) etc.

Then once you get to some reasonable formula, what's the ordering on
top of these complexities? Probably difficult.

I gave up on this for the time being. Ideas welcome.

Andrei
Well, we could see how CAS libraries handle this kind of stuff (if there _is_ one which handles it)... Really, though, with the more complex algorithms, you start running into the kinds of issues noted in the first reply to this article: http://www.perlmonks.org/?node_id=573138 Besides, is anyone actually going to specify that they need an algorithm that is O(log(n) + m^2) or whatever? Or would a function just take _two_ algorithms, assert that each is O(log(n)) and O(m^2), respectively, and then compose them itself? The complexities depend on the types of container anyway, so in general, you should get only multi-term big-O notation when you're using multiple containers (or Cartesian products of a container with itself or something like that). Can't we just make sure one container's insert() and the other container's sort() work within a certain complexity?
Multi-term complexities arise from trivial graph algorithms. They are not limited to the use of multiple containers. More precisely, the multiple terms arise because of the structure of the graph (being composed of nodes and edges); what the algorithms add are functions on nodes and edges. Unfortunately, once you have more than a single variable in your functions, the big-O expressions rapidly become inextricably complex, and can no longer map to nice abstractions like the reals + infinities + infinitesimals linear ordering. For example, two graph algorithms may be, respectively, O(V^2 + E) and O(V + E^2); it's difficult to judge based on that which one is "superior". T -- They say that "guns don't kill people, people kill people." Well I think the gun helps. If you just stood there and yelled BANG, I don't think you'd kill too many people. -- Eddie Izzard, Dressed to Kill
Dec 05 2015
parent reply BLM768 <blm768 gmail.com> writes:
On Saturday, 5 December 2015 at 22:56:23 UTC, H. S. Teoh wrote:
 Multi-term complexities arise from trivial graph algorithms. 
 They are not limited to the use of multiple containers. More 
 precisely, the multiple terms arise because of the structure of 
 the graph (being composed of nodes and edges); what the 
 algorithms add are functions on nodes and edges.
True. I don't expect that very many people would want to specify an algorithmic complexity for those operations, though. It seems much more rigidly defined than for lists, arrays, etc. The question is not really about whether "complex complexities" will exist but whether the user has a practical reason to care about specifying them.
 Unfortunately, once you have more than a single variable in 
 your functions, the big-O expressions rapidly become 
 inextricably complex, and can no longer map to nice 
 abstractions like the reals + infinities + infinitesimals 
 linear ordering. For example, two graph algorithms may be, 
 respectively, O(V^2 + E) and O(V + E^2); it's difficult to 
 judge based on that which one is "superior".
Well, if one variable is "capped" (or at least expected to be "small") it's easy enough to eliminate that term. Beyond that, there isn't necessarily a single ordering of big-O expressions, but many of them can be ordered relative to a single variable. For instance, O(n + m^2) is less complex than O(n^2 + m) with respect to n (and vice versa for m). It's trickier when expressions are more deeply nested, but if select one term (in this case, n), set all the others to be constant (since none of them depends on n), and evaluate the resulting expression tree, you should get something half-usable. Some simplifying rules may be useful. For instance, log(x^2) should approach log(x) as x approaches infinity, I think. (My calculus is a bit rusty.)
Dec 05 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/06/2015 03:47 AM, BLM768 wrote:
 log(x^2) should approach log(x) as x approaches infinity, I think. (My
 calculus is a bit rusty.)
log(x^2) = 2 log x.
Dec 05 2015
parent BLM768 <blm768 gmail.com> writes:
On Sunday, 6 December 2015 at 03:30:51 UTC, Timon Gehr wrote:
 log(x^2) = 2 log x.
Why do log rules have to make everything so simple? ;)
Dec 05 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/05/2015 04:52 PM, BLM768 wrote:
 Well, we could see how CAS libraries handle this kind of stuff (if there
 _is_ one which handles it)...
CAS = ?
 Really, though, with the more complex algorithms, you start running into
 the kinds of issues noted in the first reply to this article:
 http://www.perlmonks.org/?node_id=573138

 Besides, is anyone actually going to specify that they need an algorithm
 that is O(log(n) + m^2) or whatever? Or would a function just take _two_
 algorithms, assert that each is O(log(n)) and O(m^2), respectively, and
 then compose them itself? The complexities depend on the types of
 container anyway, so in general, you should get only multi-term big-O
 notation when you're using multiple containers (or Cartesian products of
 a container with itself or something like that). Can't we just make sure
 one container's insert() and the other container's sort() work within a
 certain complexity?
Well you'd need multiple terms if you want to say things like, "inserting a range into an array is O(array[].walkLength + r.walkLength)." When you insert a range in a binary search tree, the complexity would be O(log(array[].walkLength) * r.walkLength). Part of the art here, I feel, is knowing when to stop going too crazy about this. At this point we have a nice, round system that's simple to understand and use. Making it more complex should come only with a corresponding growth in power. Andrei
Dec 05 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
 On 12/05/2015 04:52 PM, BLM768 wrote:
 Well, we could see how CAS libraries handle this kind of stuff (if there
 _is_ one which handles it)...
CAS = ? ...
Computer Algebra System, I assume.
Dec 05 2015
prev sibling parent tsbockman <thomas.bockman gmail.com> writes:
On Saturday, 5 December 2015 at 23:55:16 UTC, Andrei Alexandrescu 
wrote:
 On 12/05/2015 04:52 PM, BLM768 wrote:
 Well, we could see how CAS libraries handle this kind of stuff 
 (if there
 _is_ one which handles it)...
CAS = ?
https://en.wikipedia.org/wiki/Computer_algebra_system
Dec 05 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/05/2015 09:48 PM, Andrei Alexandrescu wrote:
 On 12/04/2015 10:24 PM, Timon Gehr wrote:
 void foo( (BigO.linear) int n, (BigO.linear) int m);

 But UDAs for parameters are not supported.
That's actually pretty neat and easy to work around like this: void foo(int n, int m) (BigOParam!2(BigO.linear, BigO.linear); In fact I went through the implementation but soon I hit a wall: what's the _relationship_ between the two growths? It may be the sum O(m + n) but also the product O(m * n). So the operator must be encoded as well. Then what do we do with more complex relationships like O((m + n) log n) etc. Then once you get to some reasonable formula, what's the ordering on top of these complexities? Probably difficult. ...
Some upper bounds are incomparable, so there would not be a total order. But that is not a problem.
 I gave up on this for the time being. Ideas welcome.
 ...
The next step up the expressiveness scale would be to have a sum-of-products representation. Proof of concept (disclaimer: hacked together in the middle of the night, and not tested thoroughly): http://dpaste.dzfl.pl/d1512905accd I think this general approach is probably close to the sweet spot. (The implementation is not feature-complete yet, though. It would be nice if it supported automatically computing a new asymptotic runtime bound from asymptotic bounds on the arguments.)
Dec 05 2015
next sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 6 December 2015 at 03:24:24 UTC, Timon Gehr wrote:
 Some upper bounds are incomparable, so there would not be a 
 total order. But that is not a problem.
It is a problem in all cases as you usually dont have an optimal bound. And with your approach that will most certainly be guaranteed to happen. Comparing bounds does not mean you are comparing running time. O(1) implies O(f(x)), O(N) implies O(N^2). You can also get tighter bounds for specific input models.
Dec 05 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/06/2015 08:59 AM, Ola Fosheim Grøstad wrote:
 On Sunday, 6 December 2015 at 03:24:24 UTC, Timon Gehr wrote:
 Some upper bounds are incomparable, so there would not be a total
 order. But that is not a problem.
It is a problem in all cases as you usually dont have an optimal bound.
Are you complaining that the given implementation does not support 'min', or what are you trying to say here?
 And with your approach that will most certainly be guaranteed to happen.
How is that specific to my approach? I only showed a more expressive BigO implementation.
 Comparing bounds does not mean you are comparing running time.
 ...
BigO represents a set of functions. Comparing BigO checks for subset inclusion.
 O(1) implies O(f(x)), O(N) implies O(N^2).
For our purposes, O(f) = { g | ∃c. ∀x⃗. |g(x⃗)| ≤ c·|f(x⃗)|+c }. O(1) ⊆ O(f(x)), O(N) ⊆ O(N²). <= checks ⊆. == checks =. (The final implementation should use exact fractions instead of doubles.)
 You can also get tighter bounds for specific input models.
Yes, you can.
Dec 06 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/06/2015 03:39 PM, Timon Gehr wrote:
 For our purposes, O(f) = { g | ∃c. ∀x⃗. |g(x⃗)| ≤ c·|f(x⃗)|+c }.
Hm, this does not actually work too well. E.g., we want O(n+m) ⊆ O(n log m + m log n). This breaks down with that definition if we e.g. fix m=1 and let n vary. Anyway, I think this can be fixed.
Dec 06 2015
prev sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 6 December 2015 at 14:39:05 UTC, Timon Gehr wrote:
 Are you complaining that the given implementation does not 
 support 'min', or what are you trying to say here?
I am saying that comparing bounds is not the same as comparing running time of implemented algorithms. Insertion sort is both O(n^2) and O(n^3), but if you run it on a sorted array where each element have been swapped with neighbouring elements 16 times, then it is O(N). So these derived bounds are too loose to be useful, generic algorithms cannot make use of them beyond the trivial case.
 BigO represents a set of functions. Comparing BigO checks for 
 subset inclusion.
But what can you use it for? When you compose algorithms and even run an optimizer over it, then combining a O(N^2) with O(N) kan turn into O(1). You need advanced compiler support for this to be valuable.
 You can also get tighter bounds for specific input models.
Yes, you can.
Exactly, and when you compose/combine algorithms you often end up constraining the input model.
Dec 06 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/06/2015 10:35 PM, Ola Fosheim Grøstad wrote:
 On Sunday, 6 December 2015 at 14:39:05 UTC, Timon Gehr wrote:
 Are you complaining that the given implementation does not support
 'min', or what are you trying to say here?
I am saying that comparing bounds is not the same as comparing running time of implemented algorithms.
Yes, that's what you said later down the post. It's completely unrelated to the sentence you claimed was false.
Dec 06 2015
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 6 December 2015 at 23:49:00 UTC, Timon Gehr wrote:
 Yes, that's what you said later down the post. It's completely 
 unrelated to the sentence you claimed was false.
i would assume that there would have to be a usecase for something added to a standard library. Based on the presented use case it is like using the classifications "younger than 100" and "younger than 16", apply them randomly to indivduals of the same age and use the classifications for making decisions about whether they should be allowed to see adult movies or not. Putting an ordering on the classification is in that case useless.
Dec 06 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Timon Gehr <timon.gehr gmx.ch> wrote:
 On 12/05/2015 09:48 PM, Andrei Alexandrescu wrote:
 On 12/04/2015 10:24 PM, Timon Gehr wrote:
 void foo( (BigO.linear) int n, (BigO.linear) int m);
 
 But UDAs for parameters are not supported.
That's actually pretty neat and easy to work around like this: void foo(int n, int m) (BigOParam!2(BigO.linear, BigO.linear); In fact I went through the implementation but soon I hit a wall: what's the _relationship_ between the two growths? It may be the sum O(m + n) but also the product O(m * n). So the operator must be encoded as well. Then what do we do with more complex relationships like O((m + n) log n) etc. Then once you get to some reasonable formula, what's the ordering on top of these complexities? Probably difficult. ...
Some upper bounds are incomparable, so there would not be a total order. But that is not a problem.
 I gave up on this for the time being. Ideas welcome.
 ...
The next step up the expressiveness scale would be to have a sum-of-products representation. Proof of concept (disclaimer: hacked together in the middle of the night, and not tested thoroughly): http://dpaste.dzfl.pl/d1512905accd I think this general approach is probably close to the sweet spot. (The implementation is not feature-complete yet, though. It would be nice if it supported automatically computing a new asymptotic runtime bound from asymptotic bounds on the arguments.)
Brilliant! My wife has a work emergency so I've been with the kids all day, but here's what can be done to make this simpler. Use D parsing and eliminate the whole parsing routine. Add multiply and power are all defined so you only need log of bigo. Define global constants K, N, and N1 through N7. K is constant complexity all others are free variables. Then complexities are regular D expressions e.g BigO(N^2 * log(N)). On a the phone sry typos.
Dec 06 2015
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
The next step up the expressiveness scale would be to have a
sum-of-products representation.

Proof of concept (disclaimer: hacked together in the middle of the
night, and not tested thoroughly):

http://dpaste.dzfl.pl/d1512905accd

I think this general approach is probably close to the sweet spot. ...
Brilliant! My wife has a work emergency so I've been with the kids all day, but here's what can be done to make this simpler. Use D parsing and eliminate the whole parsing routine. Add multiply and power are all defined so you only need log of bigo. ...
The implementation of power on BigO given does not actually work in general (there should have been an enforcement that makes sure there is only one summand). I'll think about whether and how it can be made to work for multiple summands.
 Define global constants K, N, and N1 through N7. K is constant complexity
 all others are free variables.

 Then complexities are regular D expressions e.g BigO(N^2 * log(N)).

 On a the phone sry typos.
I generally tend to avoid DSLs based solely on operator overloading, as they don't always work and hence are awkward to evolve. Here, the biggest current nuisance is that the variable names are not very descriptive. If we'll go with a log(BigO) function, we possibly want to make BigO closed under log without approximating iterated logarithms: struct Term{ Variable n; Fraction[] exponents; // exponents[0] is exponent of n, // exponents[1] is exponent of log n, // exponents[2] is exponent of log log n, ... } Then O(log(f^c*g^d)) = O(log(f)+log(g)) = O(log(f+g)) [1], and hence every BigO has a well-defined logarithm. [1] O(log(f+g)) ⊆ O(log(f*g)) = O(log(f)+log(g)). O(log(f)+log(g)) ⊆ O(max(log(f),log(g))) = O(log(max(f,g))) ⊆ O(log(f+g)).
Dec 06 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/06/2015 06:21 PM, Timon Gehr wrote:
 The implementation of power on BigO given does not actually work in
 general (there should have been an enforcement that makes sure there is
 only one summand). I'll think about whether and how it can be made to
 work for multiple summands.
No matter, you may always use runtime assertions - after all it's all during compilation. That's the beauty of it!
 Define global constants K, N, and N1 through N7. K is constant complexity
 all others are free variables.

 Then complexities are regular D expressions e.g BigO(N^2 * log(N)).

 On a the phone sry typos.
I generally tend to avoid DSLs based solely on operator overloading, as they don't always work and hence are awkward to evolve. Here, the biggest current nuisance is that the variable names are not very descriptive.
The bright side is you get to standardize names. If you limit names to K, N, and N1 through N7 then you can always impose to APIs the meaning of these. Another bright side is people don't need to learn a new, juuust slightly different grammar for complexity expressions - just use D. For example the grammar you defined allows log n without parens - what's the priority of log compared to power etc? Why is power ^ in this notation and ^^ in D? All these differences without a distinction are gratuitous. Just use D.
 If we'll go with a log(BigO) function, we possibly want to
 make BigO closed under log without approximating iterated logarithms:

 struct Term{
      Variable n;
      Fraction[] exponents; // exponents[0] is exponent of n,
                            // exponents[1] is exponent of log n,
                            // exponents[2] is exponent of log log n, ...
 }

 Then O(log(f^c*g^d)) = O(log(f)+log(g)) = O(log(f+g)) [1], and hence
 every BigO has a well-defined logarithm.


 [1] O(log(f+g)) ⊆ O(log(f*g)) = O(log(f)+log(g)).
      O(log(f)+log(g)) ⊆ O(max(log(f),log(g)))
                       = O(log(max(f,g)))
                       ⊆ O(log(f+g)).
Yah, the stuff under log must be restricted. Here's the grammar I'm toying with: Atom ::= K | N | N1 | ... | N7 SimpleExp ::= SimpleTerm ('+' SimpleTerm)* SimpleTerm ::= SimpleFactor ('*' SimpleFactor)* SimpleFactor ::= Atom ('^^' double)? | '(' SimpleExp ')' BigO ::= Term ('+' Term)* Term ::= SimpleFactor ('*' 'log' '(' SimpleExp ')' ('^^' double)?)? (I used regex notations for "optional" and "zero or more".) This is expressible with D's native operations (so no need for custom parsing) and covers, I think, what we need. It could be further simplified if we move some of the grammar's restrictions to runtime (e.g. no need for SimpleXxx, some expressions can be forced to be simple during "runtime"). Andrei
Dec 06 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/07/2015 02:05 AM, Andrei Alexandrescu wrote:
 On 12/06/2015 06:21 PM, Timon Gehr wrote:
 The implementation of power on BigO given does not actually work in
 general (there should have been an enforcement that makes sure there is
 only one summand). I'll think about whether and how it can be made to
 work for multiple summands.
No matter, you may always use runtime assertions - after all it's all during compilation. That's the beauty of it! ...
Even better: I was wrong when I claimed it does not work. For 0<=x, it actually works as-is: O((f+g)^x) = O(max(f,g)^x) = O(max(f^x,g^x)) = O(f^x+g^x).
 Define global constants K, N, and N1 through N7. K is constant
 complexity
 all others are free variables.

 Then complexities are regular D expressions e.g BigO(N^2 * log(N)).

 On a the phone sry typos.
I generally tend to avoid DSLs based solely on operator overloading, as they don't always work and hence are awkward to evolve. Here, the biggest current nuisance is that the variable names are not very descriptive.
The bright side is you get to standardize names. If you limit names to K, N, and N1 through N7 then you can always impose to APIs the meaning of these. ...
Well, how?
 Another bright side is people don't need to learn a new, juuust slightly
 different grammar for complexity expressions - just use D. For example
 the grammar you defined allows log n without parens - what's the
 priority of log compared to power etc?
There is no priority. The parser explicitly rejects log n^x. :-)
 Why is power ^ in this notation and ^^ in D?
Because ^ is taken for bitwise xor in D due to backwards-compatibility constraints.
 All these differences without a distinction are gratuitous.
 Just use D.
 ...
D does not allow overloading of syntax to the extent necessary to make similar things really pleasant in the long run, and it has been repeatedly argued that this is a good thing; that custom parsing should be used instead. It is easy to align the parser with D syntax. Anyway, syntax is not the problem here, and the implementation can be downgraded to not support parsing and/or proper names at any point.
Dec 07 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/7/15 5:14 AM, Timon Gehr wrote:
 D does not allow overloading of syntax to the extent necessary to make
 similar things really pleasant in the long run, and it has been
 repeatedly argued that this is a good thing; that custom parsing should
 be used instead. It is easy to align the parser with D syntax. Anyway,
 syntax is not the problem here, and the implementation can be downgraded
 to not support parsing and/or proper names at any point.
I fail to see how no parens after log or "^" in lieu "^^" would make a positive difference. What would be a few examples of things that won't work pleasantly enough? I'm not sure whether the DSL argument is well applied here. Clearly using D expressions for e.g. regex or SQL syntax would be at best avoided in favor of a DSL. In this case we're defining an algebra over restricted expressions, which are a subset of the usual mathematical expressions that D's syntax already emulates. Looks like a debate on whether to choose one standard language vs. an obscure one (in this case invented ad-hoc) is starting. This is deja vu all over again :o). I hope you won't mind if I give your idea a slightly different angle. Andrei
Dec 07 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/07/2015 02:46 PM, Andrei Alexandrescu wrote:
 On 12/7/15 5:14 AM, Timon Gehr wrote:
 D does not allow overloading of syntax to the extent necessary to make
 similar things really pleasant in the long run, and it has been
 repeatedly argued that this is a good thing; that custom parsing should
 be used instead. It is easy to align the parser with D syntax. Anyway,
 syntax is not the problem here, and the implementation can be downgraded
 to not support parsing and/or proper names at any point.
I fail to see how no parens after log or "^" in lieu "^^" would make a positive difference.
Neither have I attempted to show anything like that. All arguments in this debate are obvious and boring, so no need to discuss it.
 What would be a few examples of things that won't
 work pleasantly enough?
 ...
You gave this example: http://en.cppreference.com/w/cpp/container/forward_list/insert_after 1-2) BigO("1") 3) BigO("count") 4) BigO("distance(first,last)") 5) BigO("ilist.size()") There's also this: On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
 Well you'd need multiple terms if you want to say things like,
 "inserting a range into an array is O(array[].walkLength +
 r.walkLength)." When you insert a range in a binary search tree, the
 complexity would be O(log(array[].walkLength) * r.walkLength).
BigO("array[].walkLength + r.walkLength"); BigO("log(array[].walkLength) * r.walkLength");
Dec 07 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/07/2015 09:43 AM, Timon Gehr wrote:
 1-2) BigO("1")
 3) BigO("count")
 4) BigO("distance(first,last)")
 5) BigO("ilist.size()")

 There's also this:
 On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
 Well you'd need multiple terms if you want to say things like,
 "inserting a range into an array is O(array[].walkLength +
 r.walkLength)." When you insert a range in a binary search tree, the
 complexity would be O(log(array[].walkLength) * r.walkLength).
BigO("array[].walkLength + r.walkLength"); BigO("log(array[].walkLength) * r.walkLength");
These are still expressible without a DSL: BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc. Somewhat independently of DSL or not: At this point I'm unclear whether supporting free variables with arbitrary names is a good thing. The key to unleashing the power of BigO is to compute it when combining functions, and the names seem to be specific to the function and therefore not easy to combine. Andrei
Dec 07 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/07/2015 05:15 PM, Andrei Alexandrescu wrote:
 On 12/07/2015 09:43 AM, Timon Gehr wrote:
 1-2) BigO("1")
 3) BigO("count")
 4) BigO("distance(first,last)")
 5) BigO("ilist.size()")

 There's also this:
 On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
 Well you'd need multiple terms if you want to say things like,
 "inserting a range into an array is O(array[].walkLength +
 r.walkLength)." When you insert a range in a binary search tree, the
 complexity would be O(log(array[].walkLength) * r.walkLength).
BigO("array[].walkLength + r.walkLength"); BigO("log(array[].walkLength) * r.walkLength");
These are still expressible without a DSL: BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc. ...
This just goes from one string to two strings and adds some noise on top of it. Also, now, what is D and what is in a string is arbitrary. BigO(Var.array[].walkLength + Var.r.walkLength);
 Somewhat independently of DSL or not:
Yes, notation does not matter at this stage.
 At this point I'm unclear whether
 supporting free variables with arbitrary names is a good thing.
Restricting the set of names to 8 predefined ones does not simplify anything. It just means that a mapping of predefined names to real names has to be carefully managed manually and clashes have to be avoided, all while limiting the value of BigO as documentation.
 The key
 to unleashing the power of BigO is to compute it when combining
 functions, and the names seem to be specific to the function and
 therefore not easy to combine.
 ...
Just substitute something else for those names to get rid of them. That is how passing of parameters is handled. Probably we should get some actual examples where combination should work to see what could be done. If you have: void foo(int n,int m) BigO("n*m^2"){ ... } Something like this is easy to implement: // compute runtime bound from bounds on parameters: // first expression passed is O(x^3) and second expression passed // is O(log(y)^(1/2)). enum bound = getRuntimeBound!foo(BigO("x^3"),BigO("log(y)^(1/2)")); static assert(bound == BigO("x^3*log(y)")); Note how the end user does not need to worry much about names.
Dec 07 2015
prev sibling next sibling parent ZombineDev <valid_email he.re> writes:
On Monday, 7 December 2015 at 16:15:46 UTC, Andrei Alexandrescu 
wrote:
 These are still expressible without a DSL: 
 BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc.
We can remove the use of strings if we tag walkLength with BigO: // this: BigO(Atom("array[].walkLength") + Atom("r.walkLength")) //become this: (complexity!(array[].walkLength) + complexity!(r.walkLength)) Or if we rename complexity to bigO: (bigO!(array[].walkLength) + bigO!(r.walkLength))
Dec 08 2015
prev sibling parent Jonny <Jonny nomail.com> writes:
On Monday, 7 December 2015 at 16:15:46 UTC, Andrei Alexandrescu 
wrote:
 On 12/07/2015 09:43 AM, Timon Gehr wrote:
 1-2) BigO("1")
 3) BigO("count")
 4) BigO("distance(first,last)")
 5) BigO("ilist.size()")

 There's also this:
 On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
 Well you'd need multiple terms if you want to say things like,
 "inserting a range into an array is O(array[].walkLength +
 r.walkLength)." When you insert a range in a binary search 
 tree, the
 complexity would be O(log(array[].walkLength) * r.walkLength).
BigO("array[].walkLength + r.walkLength"); BigO("log(array[].walkLength) * r.walkLength");
These are still expressible without a DSL: BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc. Somewhat independently of DSL or not: At this point I'm unclear whether supporting free variables with arbitrary names is a good thing. The key to unleashing the power of BigO is to compute it when combining functions, and the names seem to be specific to the function and therefore not easy to combine. Andrei
There are many "operations" that can be carried out on methods. Many are composable and decomposable in the exact same way and can be generalized as an algorithm: let f,f1,f2, etc be functions, if f = f1 + f2 then L(f) = L(f1) + L(f2) Hence if L is a linear operator, this always holds. Addition(+) is linear, BigO is linear. Composing linear operators is linear(but it doesn't have an inverse like addition). If D supported some generic way to handle such linear operators acting on methods, with calls to other methods as decomposing the method, one could do many cool things quite easily in D. BigO would just be one. e.g., void foo() { bar1(); bar2(); for(auto i = 1; i < 100; i++) for(auto j = 1; j < 100; j++) bar3(); } then we can see L(foo) = L(bar1) + L(bar2) + X(n^2)*L(bar3) (Here, X(n^2) is because we have a double nested for loop which multiples the complexity by n^2 for big notation. To be more precise, we should refactor all code inside the function in such a way to make things precise, i.e., void foo() { bar1(); bar2(); } void fooTemp() { for(auto i = 1; i < 100; i++) for(auto j = 1; j < 100; j++) bar3(); } which then gives the more precise decomposition as L(foo) = L(bar1) + L(bar2) + L(fooTemp) The main point of all this, is that L can be many things. If one has the complete hierarchical call stack(with root = Main) then L can be scene as recursively working on the tree. In this case, addition would rather be "insertion into tree". We could easily check relations such as if foo is called, calls, or disjoint from bar. We can, as already stated, implement complexity analysis automatically: BigO - The sup of the complexity of a function assuming all unknowns(loops, user input, unknown sub-function calls) have maximal complexity. bigO - The sup of the complexity of all functions assuming all unknowns have 0 complexity. LittleO - The inf of complexity.... litleO - ... The point, by simply implementing a decomposable structure on the "call hierarchy", one can implement all kinds of cool stuff. If it is exposed to D at run time, then even more amazing things can happen. e.g., one could implement a real time profiler. L would be an "operator" that simply sends the current ticks when first called and when returning. The "addition" is really just code that does the computations on the differences it is getting. Imagine hitting some hot key and your current app showing a tree(something like a fractal tree) where each node is a function call and sub nodes are functions that are the functions that the function calls("uses"). Color the tree based on the use rate(count how many times the function is called, or even accumulate hierarchically) or the execution time, or even BigO. You'll then see a visual of where the program is active the most. It might sort of look like the heat distribution map of the earth. I realize it is more complex to implement than I'm making it out, but it's basically tree traversal and hooks stuff. Once you start allowing meta coding, the power becomes magnified: e.g. (psuedo-code) // Define generic meta code function composer(the + in the algorithm) for BigO function!composer!BigO(functions) { let f1, ..., fn = functions return function!composer!BigO(f1) + ... + function!composer!BigO(f2) // Would need to separate parse f1 in such a way that it is composed of only calls to functions or none calls(the loop stuff I mentioned above) } // The Linear operator BigO that returns the complexity of a function f function!composer!BigO(f) { return complexity(f); } // Explicitly specify complexity for foo void foo() [function!composer!BigO() { return 0; } { ... } ------------------------------------ The above represents a mock way to allow the programmer to "hook" into the compilers call hierarchy structure. Obviously it would require some work for actual implementation. But once such a feature is implemented, the programmer can do all sorts of things. Implement "attributes"(not needed, of course), real time profiling, BigO, Code replacement/Self Modifying Programs(essentially change how a function behaves), etc... Of course, maybe we are starting to get into AI here? ;) (e.g., one could use multiple similar functions in a program for performance enhancements, but implement a few lines of code to have those functions reconfigure themselves to use the most optimal one for performance reasons) Also, why stop at functions? what about all sub-structures in the program? We could work on classes, structs, etc...
Dec 10 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
The next step up the expressiveness scale would be to have a
sum-of-products representation.

Proof of concept (disclaimer: hacked together in the middle of the
night, and not tested thoroughly):

http://dpaste.dzfl.pl/d1512905accd

I think this general approach is probably close to the sweet spot. ...
Brilliant! ...
I have noticed another thing. The comparison operator is an underapproximation (it sometimes returns NaN when ordering would actually be possible). E.g., O(n·m) ⊆ O(n²+m²), because n·m ≤ n²+m². Interesting. It would be nice if the final version had a complete decision procedure for ⊆.
Dec 06 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/06/2015 07:50 PM, Timon Gehr wrote:
 On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
The next step up the expressiveness scale would be to have a
sum-of-products representation.

Proof of concept (disclaimer: hacked together in the middle of the
night, and not tested thoroughly):

http://dpaste.dzfl.pl/d1512905accd

I think this general approach is probably close to the sweet spot. ...
Brilliant! ...
I have noticed another thing. The comparison operator is an underapproximation (it sometimes returns NaN when ordering would actually be possible). E.g., O(n·m) ⊆ O(n²+m²), because n·m ≤ n²+m². Interesting. It would be nice if the final version had a complete decision procedure for ⊆.
I think it's okay to leave N^^2 + N1 and N + N1^^2 unordered. -- Andrei
Dec 06 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/07/2015 02:07 AM, Andrei Alexandrescu wrote:
 On 12/06/2015 07:50 PM, Timon Gehr wrote:
 On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
The next step up the expressiveness scale would be to have a
sum-of-products representation.

Proof of concept (disclaimer: hacked together in the middle of the
night, and not tested thoroughly):

http://dpaste.dzfl.pl/d1512905accd

I think this general approach is probably close to the sweet spot. ...
Brilliant! ...
I have noticed another thing. The comparison operator is an underapproximation (it sometimes returns NaN when ordering would actually be possible). E.g., O(n·m) ⊆ O(n²+m²), because n·m ≤ n²+m². Interesting. It would be nice if the final version had a complete decision procedure for ⊆.
I think it's okay to leave N^^2 + N1 and N + N1^^2 unordered. -- Andrei
Yes, certainly. By complete, I mean it orders everything that can be ordered.
Dec 07 2015
prev sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Saturday, 5 December 2015 at 20:48:16 UTC, Andrei Alexandrescu 
wrote:
 Then what do we do with more complex relationships like O((m + 
 n) log n) etc.
What about a compile-time expression tree similar to how, for instance, `BaseUnit`, `ScaledUnit`, (and suggestedly `ShiftedUnit` and `LinearUnit`), are defined and used in David Nadlinger's std.units?
Mar 17
prev sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Dec 04, 2015 at 01:37:06PM -0500, Andrei Alexandrescu via Digitalmars-d
wrote:
 On 12/04/2015 11:06 AM, Andrei Alexandrescu wrote:
[...]
 Here's the algebra.
 
 Terms:
 
 1 = O(1)
 log = O(log n)
 plog = O((log n)^k)
 sqrt = O(sqrt n)
 lin = O(n)
 linlog = O(n * log n)
 linplog = O(n * (log n)^k)
 poly = O(n^k)
 exp = O(2^n)
 
 Ordering:
 
 Terms above are in increasing order.
 
 Summation:
 
 x + y = max(x, y)
 
 Product:
 
        | 1       log      plog     sqrt  lin      linlog   poly  exp
 
 -------+------------------------------------------------------------
 1      | 1       log      plog     sqrt  lin      linlog   poly  exp
 
 log    | log     plog     plog     ?     linlog   ?        poly  exp
 plog   | plog    plog     plog     ?     linplog  linplog  poly  exp
 sqrt   | sqrt    ?        ?        lin   poly     poly     poly  exp
 lin    | lin     linlog   linplog  poly  poly     poly     poly  exp
 linlog | linlog  linplog  linplog  poly  poly     poly     poly  exp
 poly   | poly    poly     poly     poly  poly     poly     poly  exp
 exp    | exp     exp      exp      exp   exp      exp      exp   exp
 
 I've left a few question marks for the tricky cases. Ideas?
[...] sqrt really belongs under poly, as far as asymptotic behaviour is concerned. Basically, O(n^j) * O(n^k) for any real j, k > 0 is asymptotically equal to O(n^(j+k)). Furthermore, O(O(n^j)^k) = O(n^(j*k)). So you can treat polynomial complexities as a field of real numbers, where + on the O(...) terms behaves like max(), * behaves like +, and function composition behaves like ^. Then exp behaves like an "infinite real", where exp > O(n^k) for all real k>0. Its inverse, log, therefore, behaves like an "infinitesimal", where O((log n)^k) for all real k>0 is less than O(n^k) for all real k>0. (Yes, even O(n^(1/1000000)) will eventually outgrow O(log n).) The log powers behave like "intermediate infinitesimals", where you have O((log n)^j) < O((log n)^k) for all positive real j < k. So these O-terms behave approximately like real numbers (poly) enhanced with infinite quantities (exp and its derivations) and infinitesimal quantities (log and its derivations), they follow the usual laws of arithmetic. Therefore, O(n^k) * O(log n) can be treated as the equivalent of a real number k + an infinitesimal L, such that k < (k+L) < k+j for all real j>0. In other words, O(n) < O(n * log n) < O(n^(1+k)) for all k>0. (Yes, even O(n^1.00000000001) will eventually outgrow O(n*log n). O(log n) behaves like an infinitesimal.) The nice thing about this is that you can simplify a lot of complicated O(...) expressions just by applying algebra as described above on the analogous {real + infinities + infinitesimals} system. Ordering relations are preserved (for the most part -- this only breaks down with pathological cases like O(sin n) which is unlikely to be ever encountered). Also, function composition between poly and non-poly complexities will generally be non-commutative, and mostly will break the + = max analogy. (But it seems unlikely, in real-world algorithms, to ever need to worry about the intricacies of exponential-time algorithms, since generally they are to be avoided where possible.) So you can get a (mostly) closed algebra just by mapping poly to the real numbers, and then adding: L = infinitesimal quantity corresponding to O(log n) E = infinite quantity corresponding to exp Various operations inside O(...) are thus mapped: + inside O(...) = max(...) * inside O(...) = + between mapped quantities O(f(g(n))) = O(f(n)) * O(g(n)) O(1) = 0 Example: is O(n^3*log(n)) better than O(n^2*(log(n))^3)? Answer: O(n^3*log(n)) maps to 3 + L, and O(n^2*(log(n))^3) maps to 2 + L^3. Since L^3 is infinitesimal, (2 + L^3) is very close to 2, whereas (3 + L) lies slightly above 3. Therefore O(n^3*log(n)) is definitely faster-growing than O(n^2*(log(n))^3). This algebra leads to various interesting questions like: - Is there an intermediate complexity that lies between poly and exp? Yes: since exp is mapped to the infinite quantity E, it follows that E/2 is still an infinite quantity (even though it's strictly less than E). E/2 corresponds to E*1/2, which is the composition of exp with sqrt, so it follows that O(n^k) < O(e^sqrt(n)) < O(e^n) for all real k>0. (There are, of course, many other possibilities.) - Similarly, the log powers O((log n)^k) are *always* slower-growing than any polynomial complexity, because L*k, being still infinitesimal, will always < j for all real j>0. So even O((log n)^10000) will not outgrow O(n^1.000000001). Multiplying with a poly function preserves this relationship: O(n^j * (log n)^k) --> j + L*k < j + m, for all real j,m>0, so O(n^j * (log n)^k) < O(n^(j+m)) for all j,m>0. Basically you're just displacing the mapped values by a constant. T -- People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird. -- D. Knuth
Dec 04 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I'll get back to this (on the phone) but this is incorrect:

sqrt really belongs under poly, as far as asymptotic behaviour is
concerned.

Fractional powers are sublinear. And sqrt times sqrt is linear which is
important.


Andrei
Dec 04 2015
parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Dec 04, 2015 at 08:03:17PM +0000, Andrei Alexandrescu via Digitalmars-d
wrote:
 I'll get back to this (on the phone) but this is incorrect:
 
 sqrt really belongs under poly, as far as asymptotic behaviour is
 concerned.
OK, I guess by poly you mean n^k for k>1. I was lumping everything under polynomial for k>0. The reason is because of the homogeneity for all values of k>0 when it comes to the algebra of complexities. Obviously, for performance-measuring purposes, k=1 is a significant landmark.
 Fractional powers are sublinear.
Wrong, O(n^(4/3)) is a fractional power, but it's not sublinear.
 And sqrt times sqrt is linear which is important.
[...] But it's just a special case of the general multiplicative->additive rule. Everyone knows 1/2 + 1/2 = 1; it doesn't seem to warrant special treatment above, say, 1/3 + 2/3 = 1, or any of the other endless identities involving 1. T -- Meat: euphemism for dead animal. -- Flora
Dec 04 2015
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 04-Dec-2015 19:06, Andrei Alexandrescu wrote:
 On 12/04/2015 01:05 AM, Tofu Ninja wrote:
 Also maybe a simpler idea would just be to annotate the the operations
 with there complexity with UDAs. That way things that really care about
 the complexity can get it, and those who don't can ignore it. It has the
 benefit of being self documenting as well.
Well look at what the cat dragged in: http://dpaste.dzfl.pl/711aecacc450
Was vaguely terrified reading this whole thread until hitting this gem. Seems like a creative use for UDA.
 That's quite promising. The code is very preliminary and uses strings
 for typical complexity values (e.g. "constant", "linear", and later
 "loglinear" etc). I need to see how to integrate this whole idea.

 Also an unpleasant problem is overloading - when present, user code
 needs to specify which overload they're referring to.

 Anyhow, this is really interesting. Thanks Tofu.


 Andrei
-- Dmitry Olshansky
Dec 04 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
 Was vaguely terrified reading this whole thread until hitting this gem. Seems
 like a creative use for UDA.
Yeah, I think it puts UDA on the map! Instead of string arguments, though, I suggest enums.
Dec 04 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 03:43 PM, Walter Bright wrote:
 On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
 Was vaguely terrified reading this whole thread until hitting this
 gem. Seems
 like a creative use for UDA.
Yeah, I think it puts UDA on the map! Instead of string arguments, though, I suggest enums.
"Even better". http://dpaste.dzfl.pl/50340e189f92 That code is actually remarkably complete, with algebra and remarkable constants. Pretty crazy, yo. Thanks all for the great ideas. D is a remarkable language. Andrei
Dec 04 2015
next sibling parent Minas Mina <minas_0 hotmail.co.uk> writes:
On Friday, 4 December 2015 at 22:48:03 UTC, Andrei Alexandrescu 
wrote:
 On 12/04/2015 03:43 PM, Walter Bright wrote:
 On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
 Was vaguely terrified reading this whole thread until hitting 
 this
 gem. Seems
 like a creative use for UDA.
Yeah, I think it puts UDA on the map! Instead of string arguments, though, I suggest enums.
"Even better". http://dpaste.dzfl.pl/50340e189f92 That code is actually remarkably complete, with algebra and remarkable constants. Pretty crazy, yo. Thanks all for the great ideas. D is a remarkable language. Andrei
Looks good :)
Dec 04 2015
prev sibling next sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/4/15 5:48 PM, Andrei Alexandrescu wrote:
 On 12/04/2015 03:43 PM, Walter Bright wrote:
 On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
 Was vaguely terrified reading this whole thread until hitting this
 gem. Seems
 like a creative use for UDA.
Yeah, I think it puts UDA on the map! Instead of string arguments, though, I suggest enums.
"Even better". http://dpaste.dzfl.pl/50340e189f92 That code is actually remarkably complete, with algebra and remarkable constants. Pretty crazy, yo. Thanks all for the great ideas. D is a remarkable language.
This looks very excellent, nice work! -Steve
Dec 04 2015
prev sibling next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Dec 04, 2015 at 05:48:03PM -0500, Andrei Alexandrescu via Digitalmars-d
wrote:
 On 12/04/2015 03:43 PM, Walter Bright wrote:
On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
Was vaguely terrified reading this whole thread until hitting this
gem. Seems like a creative use for UDA.
Yeah, I think it puts UDA on the map! Instead of string arguments, though, I suggest enums.
"Even better". http://dpaste.dzfl.pl/50340e189f92 That code is actually remarkably complete, with algebra and remarkable constants. Pretty crazy, yo. Thanks all for the great ideas. D is a remarkable language.
[...] Nice, very nice! But ... opMul? I thought that was deprecated? Shouldn't we be using opBinary!"*" instead? T -- Food and laptops don't mix.
Dec 04 2015
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 12/4/2015 2:48 PM, Andrei Alexandrescu wrote:
 On 12/04/2015 03:43 PM, Walter Bright wrote:
 On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
 Was vaguely terrified reading this whole thread until hitting this
 gem. Seems
 like a creative use for UDA.
Yeah, I think it puts UDA on the map! Instead of string arguments, though, I suggest enums.
"Even better". http://dpaste.dzfl.pl/50340e189f92 That code is actually remarkably complete, with algebra and remarkable constants. Pretty crazy, yo. Thanks all for the great ideas. D is a remarkable language.
This is very similar to the si units program Oskar Linde wrote back in 2006. Anyhow, this is very cool and should: 1. have an article written about it 2. get its own Phobos module
Dec 04 2015
prev sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 05-Dec-2015 01:48, Andrei Alexandrescu wrote:
 On 12/04/2015 03:43 PM, Walter Bright wrote:
 On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
 Was vaguely terrified reading this whole thread until hitting this
 gem. Seems
 like a creative use for UDA.
Yeah, I think it puts UDA on the map! Instead of string arguments, though, I suggest enums.
"Even better". http://dpaste.dzfl.pl/50340e189f92
Better still - no more strings: http://dpaste.dzfl.pl/5ed2b3ad3043
 That code is actually remarkably complete, with algebra and remarkable
 constants.

 Pretty crazy, yo. Thanks all for the great ideas. D is a remarkable
 language.


 Andrei
-- Dmitry Olshansky
Dec 05 2015
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 12/3/2015 10:05 PM, Tofu Ninja wrote:
 Also maybe a simpler idea would just be to annotate the the operations with
 there complexity with UDAs. That way things that really care about the
 complexity can get it, and those who don't can ignore it. It has the benefit of
 being self documenting as well.
Dang, you beat me to it!
Dec 04 2015
prev sibling parent reply tn <no email.com> writes:
On Friday, 4 December 2015 at 03:37:10 UTC, Andrei Alexandrescu 
wrote:
 On 12/3/15 10:29 PM, Jack Stouffer wrote:
 On Friday, 4 December 2015 at 02:21:12 UTC, Andrei 
 Alexandrescu wrote:
 On 12/03/2015 09:10 PM, Idan Arye wrote:
 The complexities of the operations is a property of the data 
 structure
 being used. If each collection type will have it's own set 
 of method
 names based on the complexity of operations on it, we won't 
 be able to
 have templated functions that operate on any kind of 
 collection(or at
 the very least, these functions will be really tedious to 
 code).
Your premise is right but you reach the negation of the correct conclusion. -- Andrei
How so? If a singly linked list and a doubly linked list have two different method names for the same operation, then they cannot be easily templated.
Took me a while to figure. There's a hierarchy of operations, e.g. if a collection implements insert, it automatically implements linearInsert. And so on. The collections framework provides these defaults, so client code that needs quick insert uses insert, whereas code that's fine with a linear upper bound uses linearInsert and captures both.
"I just want to insert an element. I don't care how long it takes. Why do I need to specify that it should be linear?" In my opinion, there should be "constantInsert", "linearInsert", etc. for those who care about the complexity, and "insert" should be always available.
Dec 04 2015
next sibling parent reply Jakob Ovrum <jakobovrum gmail.com> writes:
On Friday, 4 December 2015 at 09:51:05 UTC, tn wrote:
 "I just want to insert an element. I don't care how long it 
 takes. Why do I need to specify that it should be linear?"

 In my opinion, there should be "constantInsert", 
 "linearInsert", etc. for those who care about the complexity, 
 and "insert" should be always available.
In the current std.container, linearInsert aliases to the sublinear insert function when it's provided. If you don't care about running time, just use linearInsert.
Dec 04 2015
parent reply tn <no email.com> writes:
On Friday, 4 December 2015 at 09:57:48 UTC, Jakob Ovrum wrote:
 On Friday, 4 December 2015 at 09:51:05 UTC, tn wrote:
 "I just want to insert an element. I don't care how long it 
 takes. Why do I need to specify that it should be linear?"

 In my opinion, there should be "constantInsert", 
 "linearInsert", etc. for those who care about the complexity, 
 and "insert" should be always available.
In the current std.container, linearInsert aliases to the sublinear insert function when it's provided. If you don't care about running time, just use linearInsert.
I understand this. However, my point is that it seems backwards if 1) When I don't care about the complexity, then I need to specify one (e.g. linearInsert). 2) When I care and want a constant complexity, then I don't specify one (e.g. use insert instead of constantInsert). In addition, if a new container is added that only provides O(n log n) insert, then my "don't care" code that uses linearInsert does not support the new container without changes.
Dec 04 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 09:50 AM, tn wrote:
 However, my point is that it seems backwards if
 1) When I don't care about the complexity, then I need to specify one
 (e.g. linearInsert).
 2) When I care and want a constant complexity, then I don't specify one
 (e.g. use insert instead of constantInsert).
When complexity information is not present, the name of the function may carry an implicit and documented assumption of complexity bounds. -- Andrei
Dec 04 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 04:51 AM, tn wrote:
 "I just want to insert an element. I don't care how long it takes. Why
 do I need to specify that it should be linear?"
Oh but you do care.
 In my opinion, there should be "constantInsert", "linearInsert", etc.
 for those who care about the complexity, and "insert" should be always
 available.
What would be the complexity assumption of "insert"? Andrei
Dec 04 2015
parent tn <no email.com> writes:
On Friday, 4 December 2015 at 14:08:08 UTC, Andrei Alexandrescu 
wrote:
 On 12/04/2015 04:51 AM, tn wrote:
 "I just want to insert an element. I don't care how long it 
 takes. Why
 do I need to specify that it should be linear?"
Oh but you do care.
I don't, if I have a small container of constant size (or bounded by a small constant). Say, less than 10 elements. Or perhaps I just want to quickly make some prototype. And if the other part of my algorithm is exponential or even superexponential, then it is going to dominate anyway. Or should there be also baseTwoExponentialInsert etc. for the case in which I don't care as long as the complexity is at most O(2^n)?
 In my opinion, there should be "constantInsert", 
 "linearInsert", etc.
 for those who care about the complexity, and "insert" should 
 be always
 available.
What would be the complexity assumption of "insert"?
None. So in a sense that would be an alias of whateverInsert or idontcareInsert or infinityInsert.
Dec 04 2015
prev sibling next sibling parent Idan Arye <GenericNPC gmail.com> writes:
On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu 
wrote:
 I know names are something we're awfully good at discussing 
 :o). Destroy!


 Andrei
I find it ironic that this thread has moved to discuss how to name complexity/running-time...
Dec 03 2015
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/3/2015 5:27 PM, Andrei Alexandrescu wrote:
 Now this primitive may have three complexities:

 * linear in the length of r (e.g. c is a singly-linked list)

 * linear in the number of elements after r in the collection (e.g. c is an
array)

 * constant (c is a doubly-linked list)

 These complexities must be reflected in the name of the primitives. Or perhaps
 it's okay to conflate a couple of them. I know names are something we're
awfully
 good at discussing :o). Destroy!
Are you sure there are only 3 complexities? What if it's a self-balancing tree? I'm also not sure it is a good idea to put the complexity in the name of the primitive. Do any other algorithm libraries do that?
Dec 03 2015
next sibling parent reply Minas Mina <minas_0 hotmail.co.uk> writes:
On Friday, 4 December 2015 at 03:46:39 UTC, Walter Bright wrote:
 On 12/3/2015 5:27 PM, Andrei Alexandrescu wrote:
 Now this primitive may have three complexities:

 * linear in the length of r (e.g. c is a singly-linked list)

 * linear in the number of elements after r in the collection 
 (e.g. c is an array)

 * constant (c is a doubly-linked list)

 These complexities must be reflected in the name of the 
 primitives. Or perhaps
 it's okay to conflate a couple of them. I know names are 
 something we're awfully
 good at discussing :o). Destroy!
Are you sure there are only 3 complexities? What if it's a self-balancing tree? I'm also not sure it is a good idea to put the complexity in the name of the primitive. Do any other algorithm libraries do that?
I agree -- putting the complexity (eh, running time) to the primitive's name seems like a bad idea. I believe that stability is a more important "feature" of a sorting algorithm than its running time, because you can make implications about it and use them for your own algorithms (I use it for implementing delta compression) and affects the output. Running time is still a good guarantee to have, but if `sort` runs O(n^2) or O(nlogn) is not going to affect how your output will look like!
Dec 03 2015
next sibling parent reply ZombineDev <valid_email he.re> writes:
On Friday, 4 December 2015 at 07:50:19 UTC, Minas Mina wrote:
 On Friday, 4 December 2015 at 03:46:39 UTC, Walter Bright wrote:
 On 12/3/2015 5:27 PM, Andrei Alexandrescu wrote:
 Now this primitive may have three complexities:

 * linear in the length of r (e.g. c is a singly-linked list)

 * linear in the number of elements after r in the collection 
 (e.g. c is an array)

 * constant (c is a doubly-linked list)

 These complexities must be reflected in the name of the 
 primitives. Or perhaps
 it's okay to conflate a couple of them. I know names are 
 something we're awfully
 good at discussing :o). Destroy!
Are you sure there are only 3 complexities? What if it's a self-balancing tree? I'm also not sure it is a good idea to put the complexity in the name of the primitive. Do any other algorithm libraries do that?
I agree -- putting the complexity (eh, running time) to the primitive's name seems like a bad idea. I believe that stability is a more important "feature" of a sorting algorithm than its running time, because you can make implications about it and use them for your own algorithms (I use it for implementing delta compression) and affects the output. Running time is still a good guarantee to have, but if `sort` runs O(n^2) or O(nlogn) is not going to affect how your output will look like!
That's wrong. Imagine a sort method that calls to an API server to sort the numbers. Given a good internet connection, this implementation detail will not affect the correctness of the result. But I'm sure that no sane person would want to use this method. When the only job of a function is to implement an algorithm then the only thing you should care about is the time and space complexity (the correctness is given). Otherwise, designing large systems becomes impossible, because all large systems have hard performance requirements.
Dec 04 2015
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Friday, 4 December 2015 at 09:09:35 UTC, ZombineDev wrote:
 and space complexity (the correctness is given). Otherwise, 
 designing large systems becomes impossible, because all large 
 systems have hard performance requirements.
I am sorry to say this, but hard performance requirements require O(1) on everything. Big-Oh tells you essentially very little if it is more than O(1). Quick sort and insertion sort are O(N^2), bucket sort is O(N). That does not make bucket sort faster than quick sort or even insertion sort on a specific case as it is dominated by the number of possible values.
Dec 04 2015
next sibling parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Friday, 4 December 2015 at 09:17:07 UTC, Ola Fosheim Grøstad 
wrote:
 On Friday, 4 December 2015 at 09:09:35 UTC, ZombineDev wrote:
 and space complexity (the correctness is given). Otherwise, 
 designing large systems becomes impossible, because all large 
 systems have hard performance requirements.
I am sorry to say this, but hard performance requirements require O(1) on everything.
And even then you cannot assume that it is real time as the following is O(1): if (full_moon()) sleep(1000); So you can have an O(1) algorithm that occasionally triggers an expensive constant-time/memory path that causes big problems in a running system. You need a hard upper bound measured in cycles.
Dec 04 2015
prev sibling next sibling parent reply ZombineDev <valid_email he.re> writes:
On Friday, 4 December 2015 at 09:17:07 UTC, Ola Fosheim Grøstad 
wrote:
 On Friday, 4 December 2015 at 09:09:35 UTC, ZombineDev wrote:
 and space complexity (the correctness is given). Otherwise, 
 designing large systems becomes impossible, because all large 
 systems have hard performance requirements.
I am sorry to say this, but hard performance requirements require O(1) on everything. Big-Oh tells you essentially very little if it is more than O(1). Quick sort and insertion sort are O(N^2), bucket sort is O(N). That does not make bucket sort faster than quick sort or even insertion sort on a specific case as it is dominated by the number of possible values.
Well, I agree, but I didn't say hard real-time, only performance requirements that are hard to achieve because the system is large, and becuase it would cost even more if the system was larger (slower).
Dec 04 2015
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Friday, 4 December 2015 at 09:33:42 UTC, ZombineDev wrote:
 Well, I agree, but I didn't say hard real-time, only 
 performance requirements that are hard to achieve because the 
 system is large, and becuase it would cost even more if the 
 system was larger (slower).
Yes, if you are writing for large scalable systems then it is interesting to know what the ceiling is, but then you probably also want something that is no worse than O(log N). Say for a chat service you'd know that the more expensive to develop solution can scale to 10 million users (O(1)), and the less expensive do develop solution will become very expensive to run when you hit 1 million (O(log N)). So Big-Oh can be useful when you work with very large sizes and large variations, but in most cases I think it can be misleading without a good description of the actual implementation. Another very useful measure in real time is the amount of variation between repeated calls. Say if there is a guarantee of <50% variation, you can measure actual running time and add 50% headroom on the hardware requirements. Some algorithms have some fixed size tables they need to clear out every once in a while and that can be very bad.
Dec 04 2015
parent reply ZombineDev <valid_email he.re> writes:
On Friday, 4 December 2015 at 09:50:15 UTC, Ola Fosheim Grøstad 
wrote:
 On Friday, 4 December 2015 at 09:33:42 UTC, ZombineDev wrote:
 Well, I agree, but I didn't say hard real-time, only 
 performance requirements that are hard to achieve because the 
 system is large, and becuase it would cost even more if the 
 system was larger (slower).
Yes, if you are writing for large scalable systems then it is interesting to know what the ceiling is, but then you probably also want something that is no worse than O(log N). Say for a chat service you'd know that the more expensive to develop solution can scale to 10 million users (O(1)), and the less expensive do develop solution will become very expensive to run when you hit 1 million (O(log N)). So Big-Oh can be useful when you work with very large sizes and large variations, but in most cases I think it can be misleading without a good description of the actual implementation. Another very useful measure in real time is the amount of variation between repeated calls. Say if there is a guarantee of <50% variation, you can measure actual running time and add 50% headroom on the hardware requirements. Some algorithms have some fixed size tables they need to clear out every once in a while and that can be very bad.
I strongly agree with what you said earlier that typical complexity analysis is a too naive model for real-world systems. Very often (e.g. due to the nature of real hardware) your time may be dominated by constants. Or a function which looks like O(1) is sometimes O(n), due to hidden complexity. This (the fact that constants matter) is especially true when you aim for O(1). And yes, variation of execution time is also very important. However, here we're talking about API for containers and algorithms and I think that putting the complexity in the function signature is better than only using abstract data structures, because it makes you more aware of the consequences of your choice of data structures and algorithms that you make. If we can figure out a way to put even more information it may be even better.
Dec 04 2015
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Friday, 4 December 2015 at 10:35:33 UTC, ZombineDev wrote:
 However, here we're talking about API for containers and 
 algorithms and I think that putting the complexity in the 
 function signature is better than only using abstract data 
 structures, because it makes you more aware of the consequences 
 of your choice of data structures and algorithms that you make.
 If we can figure out a way to put even more information it may 
 be even better.
Well, if the algorithm can choose between containers it might be interesting to query the characteristics of a set of operations on each container. Not sure if the method name is is the best way to do it. Although I guess having a generic find(x) and find_instantly(x) would be ok, if the latter verison basically means less than 200 cycles in all cases. If it means less than 2000 cycles I think it is not so useful. Maybe it is possible to make the inference as static analysis and in addition make it possible for libraries to express various guarantees. Since it is worst case it would be acceptable that if analysis fails it will result in "unbounded".
Dec 04 2015
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, 4 December 2015 at 09:17:07 UTC, Ola Fosheim Grøstad 
wrote:
 On Friday, 4 December 2015 at 09:09:35 UTC, ZombineDev wrote:
 and space complexity (the correctness is given). Otherwise, 
 designing large systems becomes impossible, because all large 
 systems have hard performance requirements.
I am sorry to say this, but hard performance requirements require O(1) on everything.
Only when dealing with an arbitrary number of elements. O(n^2) could be fine if you know for a fact that you're always dealing with a very small number of elements. And some algorithms with worse complexity are actually faster than algorithms with lower complexity when dealing with a small number of elements - particularly since with a small number of elements, the coefficients can matter a lot more than n. So, really, to know which algorithm is appropriate, you need to know how it's actually going to be used in the program in question and how different algorithms perform there. O(1) is definitely better, but it's not necessarily required. But yes, if you're dealing with an arbitrarily large number of elements, anything worse than O(1) isn't going to cut it if you have hard performance requirements.
 Big-Oh tells you essentially very little if it is more than 
 O(1). Quick sort and insertion sort are O(N^2), bucket sort is 
 O(N). That does not make bucket sort faster than quick sort or 
 even insertion sort on a specific case as it is dominated by 
 the number of possible values.
Yeah. Really, Big-Oh tells you something about the worst case with an arbitrary number of elements. What actually happens in the program depends heavily on the number of elements which are actually involved. With large numbers of elements, Big-Oh starts mattering, but if the number of elements isn't large, then coefficients and minor implementation details of an algorithm start mattering a lot more than its conceptual worst case. Still, in general, it's better to be aware of algorithmic complexity and favor algorithms with lower complexity until you need to optimize the code based on your specific use case and determine that a higher complexity algorithm actually performs better in that specific use case. - Jonathan M Davis
Dec 04 2015
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Friday, 4 December 2015 at 15:33:56 UTC, Jonathan M Davis 
wrote:
 Only when dealing with an arbitrary number of elements. O(n^2) 
 could be fine if you know for a fact that you're always dealing 
 with a very small number of elements.
I think there was a misunderstanding about notation here. If we know that we use a small number of elements, then all operations are O(1) by definition, for any small constant.
 different algorithms perform there. O(1) is definitely better, 
 but it's not necessarily required.
Well, O(1) isn't better, it is just mandatory for anything real time. E.g: you fix your buffer to 1 seconds of audio and that is 44100 samples, then filling it is O(44100) == O(1). If am doing a scanline renderer for 2048 pixels, then an insertion sort is faster than merge sort, because most linesegments only move a few pixels per scanline. But here the problem is that there might be a 0.1% chance that most lines are almost horizontal in a variety of angles and then it breaks down, so that will be very limiting, but I still can figure out the hard maximum time required to complete, so it is still O(1) and tractable as a real time operation. If I accept arbitrary input, then I no longer can meet real time requirements, I cannot get to O(1) and therefore cannot put a fixed limit on maximum time required to complete. And that is really the only thing O(1) says: you can put a fixed limit on the time needed to complete the operation at compile time.
 actually involved. With large numbers of elements, Big-Oh 
 starts mattering, but if the number of elements isn't large, 
 then coefficients and minor implementation details of an 
 algorithm start mattering a lot more than its conceptual worst 
 case.
Yes, but most collections of entities are not very large by nature. Usually, when you try to solve a problem faster you break it down by useful segmentation and clusters (like age, kind, proximity). Complexity is mostly for thinking about what options you have when designing an algorithm. The cookbook/library approach to complexity is rather limited since they were not written for the specifics of the problem.
 Still, in general, it's better to be aware of algorithmic 
 complexity and favor algorithms with lower complexity until you 
 need to optimize the code based on your specific use case and 
 determine that a higher complexity algorithm actually performs 
 better in that specific use case.
Be aware of it, yes. Although in real code it is often best to just start out with something flexible like a dynamic array, and optimize when you know which operations are required and what operations you never will need. That often changes over time. I find that I am able to solve most of my real time problems with arrays. When I need hard requirements, I often end up using very simple datastructures like fixed sized circular buffers with a carefully calculated headroom (number of mostly unused elements) or linked lists of chunks or something really easy to reason about. During initialisation of the program it often does not matter. So if I use linear search and it completes in 100ms then fine. I don't care if there is a delay of 100ms at startup. For batch things done in Python, I just use whatever is easy, with current machines most things complete in less than a few seconds anyway. Making libraries easy to use is by far the most important parameter, I think. What would be cool is if the compiler could adjust the implementation of collections based on profiling!
Dec 04 2015
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/04/2015 02:50 AM, Minas Mina wrote:
 I agree -- putting the complexity (eh, running time) to the primitive's
 name seems like a bad idea.

 I believe that stability is a more important "feature" of a sorting
 algorithm than its running time, because you can make implications about
 it and use them for your own algorithms (I use it for implementing delta
 compression) and affects the output.

 Running time is still a good guarantee to have, but if `sort` runs
 O(n^2) or O(nlogn) is not going to affect how your output will look like!
Sort is almost always assumed to take n log n time. The problem is when you combine simpler operations, e.g. inserting elements at the front in a loop. Andrei
Dec 04 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 10:46 PM, Walter Bright wrote:
 On 12/3/2015 5:27 PM, Andrei Alexandrescu wrote:
 Now this primitive may have three complexities:

 * linear in the length of r (e.g. c is a singly-linked list)

 * linear in the number of elements after r in the collection (e.g. c
 is an array)

 * constant (c is a doubly-linked list)

 These complexities must be reflected in the name of the primitives. Or
 perhaps
 it's okay to conflate a couple of them. I know names are something
 we're awfully
 good at discussing :o). Destroy!
Are you sure there are only 3 complexities? What if it's a self-balancing tree? I'm also not sure it is a good idea to put the complexity in the name of the primitive. Do any other algorithm libraries do that?
Looks exaggerated, innit? The fact of the matter is people choose collections based on the complexity of their operations all the time. "I need to insert and remove at the front, so I'll use a list here." Or: "I need random access, I'll use a vector" etc. Not designing nomenclature for complexity leads to the usual design disasters such as providing a list with the same indexing operator as an array. Turning that on its head, if we want to allow people to design collection-independent code and mix and match collections based only on their APIs, those APIs must reflect the complexity of operations. Collection-independent code is big in my design btw. One idea is to have the very name reflect the operation. I'm thinking "insert" to mean "scoot over elements at the tail and insert the new element in the gap" and "link" to mean "create a new node and link it within this collection without scooting over anything". Then the relative costs will be implied. Another idea is to only classify operations as "quick" (expected O(1) up to O(log n)) and "not quick" (everything worse). Then we only have two categories, and "quick" will be in the name of the respective methods. Andrei
Dec 04 2015
parent reply CraigDillabaugh <craig.dillabaugh gmail.com> writes:
On Friday, 4 December 2015 at 13:58:50 UTC, Andrei Alexandrescu 
wrote:
 On 12/03/2015 10:46 PM, Walter Bright wrote:
 On 12/3/2015 5:27 PM, Andrei Alexandrescu wrote:
 Now this primitive may have three complexities:
Looks exaggerated, innit? The fact of the matter is people choose collections based on the complexity of their operations all the time. "I need to insert and remove at the front, so I'll use a list here." Or: "I need random access, I'll use a vector" etc. Andrei
My personal preference would be not to have the complexity in the names, as I prefer shorter/concise names. Typically when I am writing code using containers of any sort I will check the documentation to determine what the cost of the operations I need is and base my choice off of that. I would think (hope) most others do this too. However, I don't have a strong objection to the what is being proposed. Would you have an insertLogarithmic ( insertInverseAckerman :o) too?
Dec 04 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, 4 December 2015 at 14:51:40 UTC, CraigDillabaugh wrote:
 My personal preference would be not to have the complexity in 
 the names, as I prefer shorter/concise names. Typically when I 
 am writing code using containers of any sort I will check the 
 documentation to determine what the cost of the operations I 
 need is and base my choice off of that. I would think (hope) 
 most others do this too.  However, I don't have a strong 
 objection to the what is being proposed.
std.container puts linear and/or stable in some of its names and then creates an alias to whichever one makes sense as the default where the alias doesn't have linear or stable in the name. e.g. linearRemove becomes remove via an alias. But actually using something like stableLinearRemove in code (or stable.linear.remove) becomes hideous _very_ quickly. No one is going to like it, and it really only benefits generic code, which most container code really isn't (and given how different containers tend to be in the complexity of their operations, I question that it even makes sense to use containers generically in many cases if you actually care about efficiency). Usually the genericity is achieved via iterators or ranges, not via the code that actually operates on the container. So, while I applaud Andrei's attempt to make it so that containers can be used generically where appropriate (and having a consistent API across containers is a big win even if they're never used generically), I do fear that attempts to put the complexity and stability of the functions into the API are going to make it so unwieldy that it's useless (or at least, very un-user-friendly). Obviously, we'll have to wait and see what he comes up with, but what almost everyone is going to want is remove and insert and the like, not stable.linear.insert or stableLinearInsert or any variant on that. - Jonathan M Davis
Dec 04 2015
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/4/2015 7:11 AM, Jonathan M Davis wrote:
 On Friday, 4 December 2015 at 14:51:40 UTC, CraigDillabaugh wrote:
 My personal preference would be not to have the complexity in the names, as I
 prefer shorter/concise names. Typically when I am writing code using
 containers of any sort I will check the documentation to determine what the
 cost of the operations I need is and base my choice off of that. I would think
 (hope) most others do this too.  However, I don't have a strong objection to
 the what is being proposed.
std.container puts linear and/or stable in some of its names and then creates an alias to whichever one makes sense as the default where the alias doesn't have linear or stable in the name. e.g. linearRemove becomes remove via an alias.
Excessive use of aliases is a problem in and of itself - for example, trying to use a debugger with it, or examining the object code.
 But actually using something like stableLinearRemove in code (or
 stable.linear.remove) becomes hideous _very_ quickly. No one is going to like
 it,
I agree. Having such long names consisting of repeated use of the same words is a problem. I suggested in the pseudo namespaces thread using template parameters to express characteristics, as in: remove!(stable, linear) with sensible defaults so most of the time the user would just use: remove Generic code could use the parameters. Another alternative is to have attributes for the algorithm: stable linear remove() { ... } and then generic code could test for those attributes.
Dec 04 2015
next sibling parent BLM768 <blm768 gmail.com> writes:
On Friday, 4 December 2015 at 18:21:41 UTC, Walter Bright wrote:
 I suggested in the pseudo namespaces thread using template 
 parameters to express characteristics, as in:

     remove!(stable, linear)

 with sensible defaults so most of the time the user would just 
 use:

     remove
The nice thing about this is that it can be easy to specify which complexities an operation supports. --- void remove(complexity, T)(List!T list, size_t index) if(complexity >= Complexity.linear); //or however complexity objects work... List l; //... l.remove(3); l.remove!(Complexity.polynomial(2))(3); l.remove!(Complexity.constant)(3);//fails; there's no template specialization for this case because complex < linear.
Dec 04 2015
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, 4 December 2015 at 18:21:41 UTC, Walter Bright wrote:
 On 12/4/2015 7:11 AM, Jonathan M Davis wrote:
 std.container puts linear and/or stable in some of its names 
 and then creates an
 alias to whichever one makes sense as the default where the 
 alias doesn't have
 linear or stable in the name. e.g. linearRemove becomes remove 
 via an alias.
Excessive use of aliases is a problem in and of itself - for example, trying to use a debugger with it, or examining the object code.
Oh, I agree. But if we end up with stuff like stableLinearRemove all over the place, it's better to have the aliases than not. However, it's far better IMHO to avoid having all of those long names in the first place.
 I suggested in the pseudo namespaces thread using template 
 parameters to express characteristics, as in:

     remove!(stable, linear)

 with sensible defaults so most of the time the user would just 
 use:

     remove

 Generic code could use the parameters. Another alternative is 
 to have attributes for the algorithm:

      stable  linear remove() { ... }

 and then generic code could test for those attributes.
Either of those would be better than stableLinearRemove or stable.linear.remove. The UDAs would be more documentation friendly, though being able to pass around template arguments could be valuable for the cases where you're trying to enforce specific complexity requirements. - Jonathan M Davis
Dec 04 2015
parent reply BLM768 <blm768 gmail.com> writes:
On Friday, 4 December 2015 at 22:17:21 UTC, Jonathan M Davis 
wrote:
 Either of those would be better than stableLinearRemove or 
 stable.linear.remove. The UDAs would be more documentation 
 friendly, though being able to pass around template arguments 
 could be valuable for the cases where you're trying to enforce 
 specific complexity requirements.
It should be possible to unify the template and UDA forms. Assuming a template supportsComplexity(func, complexity) that determines whether a function or method has the specified complexity UDA (or a "faster" one), it's not hard to implement something like this: void removeWithComplexity(T, complexity)(T collection, size_t index) if(supportsComplexity!(T.remove, complexity) { collection.remove(idx); } List!int list; //... list.removeWithComplexity(Complexity.linear, 3); --- Of course, this implementation has issues with collection operations which are defined as UFCS functions (as opposed to methods), but it should be possible to get around that issue.
Dec 04 2015
parent BLM768 <blm768 gmail.com> writes:
On Saturday, 5 December 2015 at 00:13:02 UTC, BLM768 wrote:
 list.removeWithComplexity(Complexity.linear, 3);
Uh, I mean list.removeWithComplexity!(Complexity.linear)(3).
Dec 04 2015
prev sibling next sibling parent Jonny <Jonny nomail.com> writes:
On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu 
wrote:
 Consider the collections universe. So we have an imperative 
 primitive like:

 c.insertAfter(r, x)

 where c is a collection, r is a range previously extracted from 
 c, and x is a value convertible to collection's element type. 
 The expression imperatively inserts x in the collection right 
 after r.

 Now this primitive may have three complexities:

 * linear in the length of r (e.g. c is a singly-linked list)

 * linear in the number of elements after r in the collection 
 (e.g. c is an array)

 * constant (c is a doubly-linked list)

 These complexities must be reflected in the name of the 
 primitives. Or perhaps it's okay to conflate a couple of them. 
 I know names are something we're awfully good at discussing 
 :o). Destroy!


 Andrei
Why not create the capability to get the complexity by the user: writeln(c.insertAfter(r, null).complexity); If all algorithms implemented such a feature, one could have a compile time argument to display the complexity of the algorithms along with profiling. Complexity is not important except when profiling. It's also generally static depending on the types rather than the values of the types.
Dec 08 2015
prev sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu 
wrote:
 These complexities must be reflected in the name of the 
 primitives. Or perhaps it's okay to conflate a couple of them. 
 I know names are something we're awfully good at discussing 
 :o). Destroy!


 Andrei
I'm currently sitting in a software sector with one of the most demands on software stability and predictability there is. A key issue here is time-deterministic execution. I've seen no language that addresses this problem. What about adding yet another code qualifier, say deterministic, that either - forbids non-time-determinstic execution paths such as `if-statements` or perhaps better - makes the compiler generate code that strives to be as deterministic as possible, for instance executing all brances of a conditional statement. and of course checking this transitively over function calls. This would have to take into account direct or in-direct recursions which might become complicated. I'm of course also aware of the inherent variations in microcode execution time for most CPU architectures of today. Despite this fact, safety-critical systems (in for instance aerospace) uses the architectures and are in need of tools that can do as good as currently possible at least at the source code level. Destroy!
Mar 17