4 ms·

But... this isn't actually a vector. It stands to reason that if you use a different data structure then you will get different timing properties, but you are n

But... this isn't actually a vector. It stands to reason that if you use a different data structure then you will get different timing properties, but you are not comparing like-for-like.

alkonaut 12y ago
What is a vector? There is nothing that says a vector has to be a sequentially stored array. If you agree that the interface is a vector interface, then it "is" a vector.
- joosters 12y ago
  That's pretty much the definition of it. It's what just about every language out there calls a vector. If you want a blackbox object that has Lookup(), Add() and Set() but with no guarantees about the underlying algorithm, you should probably avoid calling it a vector...
  - alkonaut 12y ago
    A "list" can be a linked list, an array based list and so on. Would a data structure stored in an array but not supporting the correct interface be a "vector" because the secret implementation is an array?
  - zamalek 12y ago
    Queues and stacks are typically implemented using arrays. Should a queue or stack that uses a linked list (which is how you make them lock-free, or one way to make them immutable) be called something else then?
  - SideburnsOfDoom 12y ago
    > If you want a blackbox object that has Lookup(), Add() and Set() but with no guarantees about the underlying algorithm, you should probably avoid calling it a vector. "Vector" here is an interface. The equivalent, e.g. "interface ILinkedListVector" is considered bad practice, i.e. you do want an interface to be a back box and not leak implementation details. if it has the right operations, "Vector" (actually more like "IVector<T>") is an acceptable interface name.
- deleted 12y ago
  [deleted]
- EpicEng 12y ago
  Right, except for the fact that they always are made to behave that way, and if I were using a language with a "vector" type which performed like a linked list i would probably stop using that language altogether.
  - nickik 12y ago
    What? The standard Clojure vector is like that. Nobody has a problem with it. It has good performance. Why should you care about the memory layout? If you are not doing math on pointer, it should not matter.
    - ygra 12y ago
      It has nothing to do with pointers, but memory access patterns can have a huge performance impact. Iterate over a large array, and do the same over a large linked list. The latter cannot make use of the CPU cache in any meaningful way, for example.
      - alkonaut 12y ago
        And the linked list can share storage between different lists which the straight array cannot. There are always benefits and drawbacks with different structures. "list" doesn't say what data structure is used, it only describes the semantics (an ordered collection of items). It's the same with a vector.
      - nickik 12y ago
        I agree, memory access patterns can have a huge performacne impact. The cache is importent but its not as simple as you think. Im not gone explain to you why it work, but see paper [1]. Its not about the clojure vector, but basiclly the same and he explains performance and he it is quite fast for lookup. Adding is also quite fast, both for immutable and the mutable case. [1] http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
  - alkonaut 12y ago
    much of the point of immutable data structures is to re-use the storage of items. A mutable vector is usually just a continuous array for that reason (can't re-use so just as well to optimize for compactness and access). But an immutable vector isn't as natural to store in an array. The opinion that vector must equal array is presumably because people have used mutable vectors in e.g Java or C++ and assumed the underlying data structure is the same in other contexts. A mutable List is very natural to implement array based, but an immutable List is usually not. It's the same thing.

But... this isn't actually a vector. It stands to reason that if you use a different data structure then you will get different timing properties, but you are not comparing like-for-like.

alkonaut 12y ago

What is a vector? There is nothing that says a vector has to be a sequentially stored array. If you agree that the interface is a vector interface, then it "is" a vector.

joosters 12y ago
That's pretty much the definition of it. It's what just about every language out there calls a vector. If you want a blackbox object that has Lookup(), Add() and Set() but with no guarantees about the underlying algorithm, you should probably avoid calling it a vector...
- alkonaut 12y ago
  A "list" can be a linked list, an array based list and so on. Would a data structure stored in an array but not supporting the correct interface be a "vector" because the secret implementation is an array?
- zamalek 12y ago
  Queues and stacks are typically implemented using arrays. Should a queue or stack that uses a linked list (which is how you make them lock-free, or one way to make them immutable) be called something else then?
- SideburnsOfDoom 12y ago
  > If you want a blackbox object that has Lookup(), Add() and Set() but with no guarantees about the underlying algorithm, you should probably avoid calling it a vector. "Vector" here is an interface. The equivalent, e.g. "interface ILinkedListVector" is considered bad practice, i.e. you do want an interface to be a back box and not leak implementation details. if it has the right operations, "Vector" (actually more like "IVector<T>") is an acceptable interface name.
deleted 12y ago
[deleted]
EpicEng 12y ago
Right, except for the fact that they always are made to behave that way, and if I were using a language with a "vector" type which performed like a linked list i would probably stop using that language altogether.
- nickik 12y ago
  What? The standard Clojure vector is like that. Nobody has a problem with it. It has good performance. Why should you care about the memory layout? If you are not doing math on pointer, it should not matter.
  - ygra 12y ago
    It has nothing to do with pointers, but memory access patterns can have a huge performance impact. Iterate over a large array, and do the same over a large linked list. The latter cannot make use of the CPU cache in any meaningful way, for example.
    - alkonaut 12y ago
      And the linked list can share storage between different lists which the straight array cannot. There are always benefits and drawbacks with different structures. "list" doesn't say what data structure is used, it only describes the semantics (an ordered collection of items). It's the same with a vector.
    - nickik 12y ago
      I agree, memory access patterns can have a huge performacne impact. The cache is importent but its not as simple as you think. Im not gone explain to you why it work, but see paper [1]. Its not about the clojure vector, but basiclly the same and he explains performance and he it is quite fast for lookup. Adding is also quite fast, both for immutable and the mutable case. [1] http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
- alkonaut 12y ago
  much of the point of immutable data structures is to re-use the storage of items. A mutable vector is usually just a continuous array for that reason (can't re-use so just as well to optimize for compactness and access). But an immutable vector isn't as natural to store in an array. The opinion that vector must equal array is presumably because people have used mutable vectors in e.g Java or C++ and assumed the underlying data structure is the same in other contexts. A mutable List is very natural to implement array based, but an immutable List is usually not. It's the same thing.