5 ms·

Data Structures in JavaScript

147 points by shawndumas 11y ago

drabiega 11y ago
It looks like this is a teaching exercise more than anything, but it should be noted that the implementations are not great. For instance, the set uses an array based implementation instead of hash based. In JavaScript the hash based implementation is pretty trivial to write and some quick testing in node shows that it is dramatically faster.
- ChrisDutrow 11y ago
  Yeah, I thought that was strange to use a list for the set implementation too. Average set addition and search should be O(1) if using a hash table. O(n) is a problem. Glad they put that clearly at the top though.
- Kinnard 11y ago
  Could you share your test code?
  - deleted 11y ago
    [deleted]
- vkjv 11y ago
  Unless by "hash based" you mean just using `new Set()`, I'm not aware of a way to do this generically. Using a `{}` for this would only work for a set of strings and things that can be uniquely coerced into strings. Otherwise, looping over arrays is your only option. Care to elaborate?
  - nkoren 11y ago
    > Using a `{}` for this would only work for a set of strings and things that can be uniquely coerced into strings. The code they use has the same limitation. It adds / removes / ensures the uniqueness of elements in the set by using Array.indexOf(...), which only works for strings and things that can be uniquely coerced into strings. So, given this limitation, using an Object-based set would be vastly more performant.
    - dsp1234 11y ago
      var set = [] var foo = {foot: 1} var bar = {bart: 2} set.push(foo) set.indexOf(foo) //0 set.indexOf(bar) //-1 "indexOf() compares searchElement to elements of the Array using strict equality (the same method used by the ===, or triple-equals, operator)."[0] MDN has the link to the ES5 specification, but the key part is 9(c)(ii): "Let same be the result of applying the Strict Equality Comparison Algorithm to searchElement and elementK." [0] - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
      - nkoren 11y ago
        Hmm, and yet: var elem = {foo:"bar"} var set = [elem] set.indexOf(elem) // 0 set.indexOf({foo:"bar"}) // -1 So I guess the strict equality comparison is using some kind of internal objectId rather than the property name and values of the objects? I guess depend on how you want to define "uniqueness" for your set...
        dsp1234 11y ago
        Objects in JavaScript use referential equality when checking for strict equality, which indexOf uses. In your code, 'elem' and '{foo:"bar"}' are different objects which is why your code doesn't work as expected. So var x = {foo:"bar"} var y = {foo:"bar"} var z = x x === y //false x === z //true This is specified in the ES3 document[0] at 11.9.6(13): "13. Return true if x and y refer to the same object or if they refer to objects joined to each other (see 13.1.2). Otherwise, return false." [0] - http://www.ecma-international.org/publications/files/ECMA-ST-ARCH/ECMA-262,%203rd%20edition,%20December%201999.pdf http://www.ecma-international.org/publications/files/ECMA-ST...
    - tlb 11y ago
      Don't forget to mangle the strings, otherwise inserting things with names meaningful to Javascript ('hasOwnProperty', '__prototype__') can cause great suffering.
  - mistercow 11y ago
    You can do it the way a lot of libraries do where you require that anything you want in a set implement an interface for hashing and equality testing. Then you use an object with hashes for keys and arrays for values.
  - aaco 11y ago
    Google Closure Library does this in goog.structs.Set with an interesting generic solution. A string key for the underlying map is generated based on the data type of the element being added in the set. If you're adding an object into the set, the object is mutated so that it stores a unique ID. The object's unique ID is used to form the string key that will identify this object in the set. Note how goog.structs.Set.getKey_ is used in the add() method: https://github.com/google/closure-library/blob/v20160125/closure/goog/structs/set.js#L59 https://github.com/google/closure-library/blob/v20160125/clo... This is how the library obtains the unique ID of an object: https://github.com/google/closure-library/blob/v20160125/closure/goog/base.js#L1653 https://github.com/google/closure-library/blob/v20160125/clo...
    - dsp1234 11y ago
      I wonder if that's a problem with stuff like immutibleJS since the object itself is permanently mutated as part of being added to the set. Also, if this was being done for ES5+ code, then either setting that property to non-enumerable or using something like Symbols would be cool since it would hopefully have a reduced impact on other code.
      - dcherman 11y ago
        Depending on the implementation, yup. Since both of the most popular Immutable libraries that I know of (Immutable.js, mori) have their own API for setting properties via a `.set` method, it would not be unreasonable for them to use `Object.freeze` in order to make raw mutations throw an error. Both libraries provide their own implementation of a Set though, so in practice you would just use the library provided one.
- tlb 11y ago
  And the Queue has an O(n) remove operation, because it just uses Array.unshift. There are plenty of implementations with O(1) remove, like http://code.stephenmorley.org/javascript/queues/ http://code.stephenmorley.org/javascript/queues/
eastbayjake 11y ago
It seems like cheating to do a Hash Table using JavaScript objects, since it's basically giving you all the hashing magic for free. It'd be cool if the example actually used an array and a hash function -- even a black box one -- to show how collisions and lookups are handled. (When I've implemented Hash Tables in JavaScript in the past, I've also included functionality to rehash the entire table into a larger array as it gets more than 25-50% full... but can't remember off the top of my head what's the mathematically optimal point to rehash.)
- masklinn 11y ago
  > When I've implemented Hash Tables in JavaScript in the past, I've also included functionality to rehash the entire table into a larger array as it gets more than 25-50% full... but can't remember off the top of my head what's the mathematically optimal point to rehash. The load factor (entries/bucket before you resize) varies greatly depending on the hashmap's addressing and collision resolution. Robin-hood hashing allows ridiculously high open-addressing load factors for instance (above 0.9 on an open-addressing linear-probed map, an open-addressing hash table can't go beyond 1), meanwhile separate-chaining allows load factors way above 1 (buckets are sequences and conflicting entries are appended to the sequence)
gravypod 11y ago
I've been toying around with the idea in my head of building a small OS kernel in Javascript. I'd use grub to boot into it, ductape [0] to start an os.js or something, and then just implement everything from there. These data-structure implementations make me feel that, even though it is crazy, it might just work. This seems to have come out very clean and easy to implement. [0] - http://duktape.org/ http://duktape.org/
- woah 11y ago
  But why?
  - gravypod 11y ago
    It would be simple to get anyone into OS development. The only easier language I can find to teach someone is Python, and that doesn't have such an easily portable runtime. JavaScript is great because you can learn it in the afternoon and master it in a few years and has a nice subset of lisp-like features. It would be a toy to prototype in. Easy to use, and easy to modify. Nothing serious.
    - srpeck 11y ago
      Check out https://github.com/NodeOS/NodeOS https://github.com/NodeOS/NodeOS
      - gravypod 11y ago
        I just spent a few minutes looking around that and it seems like it has a lot of extra stuff piled on to make it easier for experienced developers, but that would inversely effect someone like me. I looked around in there and have no idea how any of that works or how any of the modules relate.
  - d0m 11y ago
    For me it'd be a great way to learn about OS with something I'm already really familiar with, and also something that I can easily hack on. I.e. Similar reasons why I much more prefer stumpwn to ratpoison.

147 points by shawndumas 11y ago

It looks like this is a teaching exercise more than anything, but it should be noted that the implementations are not great. For instance, the set uses an array based implementation instead of hash based. In JavaScript the hash based implementation is pretty trivial to write and some quick testing in node shows that it is dramatically faster.

ChrisDutrow 11y ago
Yeah, I thought that was strange to use a list for the set implementation too. Average set addition and search should be O(1) if using a hash table. O(n) is a problem. Glad they put that clearly at the top though.
Kinnard 11y ago
Could you share your test code?
- deleted 11y ago
  [deleted]
vkjv 11y ago
Unless by "hash based" you mean just using `new Set()`, I'm not aware of a way to do this generically. Using a `{}` for this would only work for a set of strings and things that can be uniquely coerced into strings. Otherwise, looping over arrays is your only option. Care to elaborate?
- nkoren 11y ago
  > Using a `{}` for this would only work for a set of strings and things that can be uniquely coerced into strings. The code they use has the same limitation. It adds / removes / ensures the uniqueness of elements in the set by using Array.indexOf(...), which only works for strings and things that can be uniquely coerced into strings. So, given this limitation, using an Object-based set would be vastly more performant.
  - dsp1234 11y ago
    var set = [] var foo = {foot: 1} var bar = {bart: 2} set.push(foo) set.indexOf(foo) //0 set.indexOf(bar) //-1 "indexOf() compares searchElement to elements of the Array using strict equality (the same method used by the ===, or triple-equals, operator)."[0] MDN has the link to the ES5 specification, but the key part is 9(c)(ii): "Let same be the result of applying the Strict Equality Comparison Algorithm to searchElement and elementK." [0] - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
    - nkoren 11y ago
      Hmm, and yet: var elem = {foo:"bar"} var set = [elem] set.indexOf(elem) // 0 set.indexOf({foo:"bar"}) // -1 So I guess the strict equality comparison is using some kind of internal objectId rather than the property name and values of the objects? I guess depend on how you want to define "uniqueness" for your set...
      - dsp1234 11y ago
        Objects in JavaScript use referential equality when checking for strict equality, which indexOf uses. In your code, 'elem' and '{foo:"bar"}' are different objects which is why your code doesn't work as expected. So var x = {foo:"bar"} var y = {foo:"bar"} var z = x x === y //false x === z //true This is specified in the ES3 document[0] at 11.9.6(13): "13. Return true if x and y refer to the same object or if they refer to objects joined to each other (see 13.1.2). Otherwise, return false." [0] - http://www.ecma-international.org/publications/files/ECMA-ST-ARCH/ECMA-262,%203rd%20edition,%20December%201999.pdf http://www.ecma-international.org/publications/files/ECMA-ST...
  - tlb 11y ago
    Don't forget to mangle the strings, otherwise inserting things with names meaningful to Javascript ('hasOwnProperty', '__prototype__') can cause great suffering.
- mistercow 11y ago
  You can do it the way a lot of libraries do where you require that anything you want in a set implement an interface for hashing and equality testing. Then you use an object with hashes for keys and arrays for values.
- aaco 11y ago
  Google Closure Library does this in goog.structs.Set with an interesting generic solution. A string key for the underlying map is generated based on the data type of the element being added in the set. If you're adding an object into the set, the object is mutated so that it stores a unique ID. The object's unique ID is used to form the string key that will identify this object in the set. Note how goog.structs.Set.getKey_ is used in the add() method: https://github.com/google/closure-library/blob/v20160125/closure/goog/structs/set.js#L59 https://github.com/google/closure-library/blob/v20160125/clo... This is how the library obtains the unique ID of an object: https://github.com/google/closure-library/blob/v20160125/closure/goog/base.js#L1653 https://github.com/google/closure-library/blob/v20160125/clo...
  - dsp1234 11y ago
    I wonder if that's a problem with stuff like immutibleJS since the object itself is permanently mutated as part of being added to the set. Also, if this was being done for ES5+ code, then either setting that property to non-enumerable or using something like Symbols would be cool since it would hopefully have a reduced impact on other code.
    - dcherman 11y ago
      Depending on the implementation, yup. Since both of the most popular Immutable libraries that I know of (Immutable.js, mori) have their own API for setting properties via a `.set` method, it would not be unreasonable for them to use `Object.freeze` in order to make raw mutations throw an error. Both libraries provide their own implementation of a Set though, so in practice you would just use the library provided one.
tlb 11y ago
And the Queue has an O(n) remove operation, because it just uses Array.unshift. There are plenty of implementations with O(1) remove, like http://code.stephenmorley.org/javascript/queues/ http://code.stephenmorley.org/javascript/queues/

eastbayjake 11y ago

It seems like cheating to do a Hash Table using JavaScript objects, since it's basically giving you all the hashing magic for free. It'd be cool if the example actually used an array and a hash function -- even a black box one -- to show how collisions and lookups are handled. (When I've implemented Hash Tables in JavaScript in the past, I've also included functionality to rehash the entire table into a larger array as it gets more than 25-50% full... but can't remember off the top of my head what's the mathematically optimal point to rehash.)

masklinn 11y ago
> When I've implemented Hash Tables in JavaScript in the past, I've also included functionality to rehash the entire table into a larger array as it gets more than 25-50% full... but can't remember off the top of my head what's the mathematically optimal point to rehash. The load factor (entries/bucket before you resize) varies greatly depending on the hashmap's addressing and collision resolution. Robin-hood hashing allows ridiculously high open-addressing load factors for instance (above 0.9 on an open-addressing linear-probed map, an open-addressing hash table can't go beyond 1), meanwhile separate-chaining allows load factors way above 1 (buckets are sequences and conflicting entries are appended to the sequence)

gravypod 11y ago

I've been toying around with the idea in my head of building a small OS kernel in Javascript. I'd use grub to boot into it, ductape [0] to start an os.js or something, and then just implement everything from there. These data-structure implementations make me feel that, even though it is crazy, it might just work. This seems to have come out very clean and easy to implement. [0] - http://duktape.org/ http://duktape.org/

woah 11y ago
But why?
- gravypod 11y ago
  It would be simple to get anyone into OS development. The only easier language I can find to teach someone is Python, and that doesn't have such an easily portable runtime. JavaScript is great because you can learn it in the afternoon and master it in a few years and has a nice subset of lisp-like features. It would be a toy to prototype in. Easy to use, and easy to modify. Nothing serious.
  - srpeck 11y ago
    Check out https://github.com/NodeOS/NodeOS https://github.com/NodeOS/NodeOS
    - gravypod 11y ago
      I just spent a few minutes looking around that and it seems like it has a lot of extra stuff piled on to make it easier for experienced developers, but that would inversely effect someone like me. I looked around in there and have no idea how any of that works or how any of the modules relate.
- d0m 11y ago
  For me it'd be a great way to learn about OS with something I'm already really familiar with, and also something that I can easily hack on. I.e. Similar reasons why I much more prefer stumpwn to ratpoison.