Skip to main content

News

Topic: Link.js v0.4.2 (Read 95644 times) previous topic - next topic

0 Members and 1 Guest are viewing this topic.
Re: [code] Query.js for Sphere
Reply #45
Do you have an API listing for link? Or some simple explained examples?
  • Last Edit: January 14, 2014, 02:44:37 am by Flying Jester

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Query.js for Sphere
Reply #46
A good API is on the github page. Examples, well... you can try the ones from the front post. The semantics have changed.

Query.from(array).where(even).foreach(print);

Is now:

Link(array).where(even).each(print);

I could add a few examples to the github page, too. :) (I might rewrite the first post with Link details and kinda ditch Query altogether.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: [code] Query.js for Sphere
Reply #47
Or just split off the topic, and leave the Query bit for posterity?  :)

Thanks. I'm definitely going to give this a try.

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Link.js v0.2.1
Reply #48
Nah, I'll just post Query as legacy code beneath it. Link has gotten good enough to be quite beneficial - I want to preserve the discussion on how I went from the slow piece of crap that is query.js to the magnificent link.js /gloat :P.

Edit: as of 0.2.2 the speeds are even faster:

Version 0.2.0:
Code: (text) [Select]

Link map-filter-map-each: 0.6099999998696148ms index.html:37
Lazy map-filter-map-each: 1.0999999986961484ms index.html:37


Version 0.2.2:
Code: (text) [Select]

Link map-filter-map-each: 0.18000000156462193ms (index):34
Lazy map-filter-map-each: 1.180000000167638ms (index):34


The stark speedup has a lot to do with the static function creation and function inlining things I've added since 0.2.0, oh, and the optimizations it makes. I'm loving Chrome now!
  • Last Edit: January 15, 2014, 03:58:59 am by Radnen
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: [code] Link.js v0.2.2
Reply #49
Here's a question:

What would the best way be, using Link, to remove all items from an array that have a specific value for certain properties?

EDIT:

It seems that uniq() likes to trim out objects that aren't actually duplicates (either by content or identity), too.
  • Last Edit: January 15, 2014, 12:46:24 am by Flying Jester

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Link.js v0.2.2
Reply #50

Here's a question:

What would the best way be, using Link, to remove all items from an array that have a specific value for certain properties?


Link works on a "copy" (not really, but it generates a copy as it works) of the array, so unfortunately it doesn't do any destructive changes. It's both a blessing and a curse depending on who you ask. So I'm a bit torn on that part of it right now since I myself am struggling with the concept of efficiently removing items. I might add in something like that, it may not be common to such libraries like Lazy, but you and me, seem to need it - since it's good for games.

Now, to delete things we can do this:
Code: (javascript) [Select]

// figures out what to delete, by populating an array of true/false values.
function deletable(a, b) {
    if (b needs deletion) a.push(true);
    else a.push(false);
    return a;
}

// runs the query:
var items = Link(array).reduce(deletable, []);

// performs the deletions:
for (var i = 0; i < items.length; ++i) { if (items[i]) { array.splice(i, 1); i--; } }


We need to figure out what to delete before we delete it, because deleting things as the query runs destroys it's stopping condition and can muddle up results. To do it I use reduce: reduce is used to create something. It takes two inputs from the original array and turns them into a single output (effectively reducing the size), however if you start it off with an array or object, we can do interesting things with values on an as-they-are-seen basis. The bad thing is we are effectively traversing the entire source array twice, which is no-good performance wise.

Also, notice there is no filter clause. It might be better to filter things out before calling reduce, but then you are working off a modified version of the array... a filtered version of it to be precise. So it'll tell you nothing as to where to snip an item out, sadly. (again hence the speed).

Ok... I convinced myself removing items is really terrible in these kinds of schemes... I can try to figure out deletion, but it get's tricky in the whole lazy-execution scheme. It might be doable, though.

Also, in my experience Array.splice is terribly, terribly slow. It turns out recreating a new array is better. Hmm...

Code: (javascript) [Select]

// populates an array with items that are okay to keep:
function deleted(a, b) {
    if (b does not need deletion) a.push(b);
    return a;
}

// runs the query:
array = Link(array).reduce(deleted, []);


The above might be faster if you are okay with replacing the original array with an entirely new one! (This now sounds more like a reduce-y type of thing to do). :)

In fact it get's even faster if we continue this line of thought:
Code: (javascript) [Select]

// runs the query:
array = Link(array).where(what-to-delete).toArray();


Now it'll be flying... Esp. if it's an array of objects. Since it doesn't need to recreate the objects, recreating an array is a low-cost alternative to hand-picking items to remove. It may in fact be the best solution, and what Link would do internally, anyways.

If you want to remove a single item... or only a few, we can do this:
Code: (javascript) [Select]

var bob = { name: "bob", dead: false };
var array = [bob, { name: "sue", dead: true }, { name: "ann", dead: false }, { name: "tom", dead: true }];

// runs the query:
array.splice(Link(array).indexOf(bob), 1); // straight-up removal.

// bob is now removed

// or use a new feature:
array.splice(Link(array).indexOf("dead", true), 1); // deletes an object with the first property of "dead" set to true.

// sue is now removed

// alternative, for deleting several items (also the safest solution since it doesn't assume the object is in the list):
var i;
while (i = Link(array).indexOf("dead", true) >= 0) { array.splice(i, 1); }

// sue and tom are now removed.


So there, I think I exhausted many possibilities! :)


It seems that uniq() likes to trim out objects that aren't actually duplicates (either by content or identity), too.


uniq is still a WIP, it filters out identical strings, and numbers only. I'll have to look into how other libraries do it. It might be cheating, but if the uniq doesn't work as other standard libraries do, it can mean bad things. I'm sure there is a good, general, algorithm somewhere. That said my current approach is not too bad, just a super-lite version of the real deal.

So, my current to-do list:
1. Implement skip()
2. Implement a destructive API - there may be no need...
3. Improve reduce
4. Improve uniq
  • Last Edit: January 15, 2014, 03:56:07 am by Radnen
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: [code] Link.js v0.2.2
Reply #51
I would be satisfied if, on objects, uniq only filtered out objects that had the same identity.

Alternatively, you could try something like:

Code: [Select]

var same = true;
for(var i in object1){
  for(var e in object2){
    if(object1[i]!==object2[e])
      same=false;
  }
}

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Link.js v0.2.2
Reply #52
Wait, are your objects made like so:

Code: (javascript) [Select]

var list = [p1, p1, p2, p1, p2, p3];
Link(list).uniq().toArray(); // := [p1, p2, p3]


Because then I can do reference checking which is 1000 times faster. True unique filtering is time consuming! I see all kinds of ideas online, and - even - yours will slow down a lot from going through their properties or recursing through their prototypes (etc).

Is:
Code: (javascript) [Select]

{ x: 0, y: 0 } == { x: 0, y: 0 } // yes
{ y: 0, x: 0 } == { x: 0, y: 0 } // yes?
{ x: 0, y: 0 } == { x: 0, y: 0 } (prototype different) // ex: new Point() vs. new Vertex()???
// What about different names for methods that do the same thing???


My code currently checks if the object is a property and, if so, filters it really fast. If not, it then puts it on a reference list and checks against that to see if the reference is being used. Now, if I employed your technique, it's going to take a lot of time to filter two unique items. A list of a hundred or a thousand may be the maximum for good operation. But 10000 items... and it's not so good anymore. It depends on how large of an object they are too!

The one other solution is to have a unique filtering callback:
Code: (javascript) [Select]

function my_filter(item, other) {
    for (var i in item) {
        var o = item[i];
        for (var e in other) {
            if (o != other[e]) return false;
        }
    }
    return true;
}

var array = Link(array).uniq(my_filter).toArray();


Then that way you can at least compare two items with your own method. It will run the callback against all other items that are objects to determine if it is indeed a unique element, for each element. This doesn't make it any faster, but at least you can fine-tune the check and compare against certain values. Then, then you can do something like this to speed it up a bit:

Code: (javascript) [Select]

var array = Link(array).filter(stuff).uniq(my_filter).toArray();


The filter above can filter out items with properties you know to be different among items to reduce your chances of uniq going over items that are largely different. It might help, it might not.

Edit:
If you know your items are of the same structure, this is faster:
Code: (javascript) [Select]

function my_filter(item, other) {
    for (var i in item) {
        if (item[i] != other[i]) return false;
    }
    return true;
}


And, so I think I'm going with the callback approach. It's really up to the user what they want to look for between two items that determines uniqueness. Do you need full recursive checks or surface level checks? Reference checks or just primitive checks? Prototypical checks or JSON-like stringify checks? There are no clear winners here how uniqueness is resolved. It's up to the data and what you intend to do with it.

Look out for v0.2.3 soonish. Ok, and it's up!
  • Last Edit: January 15, 2014, 06:46:45 am by Radnen
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: [code] Link.js v0.2.2
Reply #53

Wait, are your objects made like so:

Code: (javascript) [Select]

var list = [p1, p1, p2, p1, p2, p3];
Link(list).uniq().toArray(); // := [p1, p2, p3]


Because then I can do reference checking which is 1000 times faster. True unique filtering is time consuming! I see all kinds of ideas online, and - even - yours will slow down a lot from going through their properties or recursing through their prototypes (etc).



Generally speaking, yes. That's what I initially thought uniq would check for.



And, so I think I'm going with the callback approach. It's really up to the user what they want to look for between two items that determines uniqueness. Do you need full recursive checks or surface level checks? Reference checks or just primitive checks? Prototypical checks or JSON-like stringify checks? There are no clear winners here how uniqueness is resolved. It's up to the data and what you intend to do with it.


A callback would be fine. In my case (and I would expect many others), There are certain properties I don't consider important for uniqueness. There are also a few cases where this would be a useful shorthand for when I would like to only check the uniqueness of a certain property or properties of the elements.

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Link.js v0.2.3
Reply #54
Well, it does that now.

Uniq API:
Code: (javascript) [Select]

Link(array).uniq(); // does reference checks, or filters out primitives.
Link(array).uniq(test); // uses test to filter unique objects, or filters out primitives.


My next task is to put up a definitive API. I'll probably do that as a github wiki page.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: [code] Link.js v0.2.3
Reply #55
Here's something that would be cool. Could you add orthogonal foreach?

As in, a foreach where the function takes two arguments, each one an item from two lists, and it is called with every combination? Or would that be slower than just calling toArray on both Link objects and doing a nested loop?

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Link.js v0.2.3
Reply #56
You might get away with using reduce, and go through all of the combinations:

Code: (javascript) [Select]

function stuff(a, b) {
    for (var i = 0; i < a.length; ++i) { b.prop += a[i].prop; }
    return a;
}

Link(array1).reduce(stuff, array2).each(action);


It wouldn't work on a list of primitives though since they are not passed by reference.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: [code] Link.js v0.2.3
Reply #57
You could do that with zip().

Code: (javascript) [Select]

Link(array1).zip(array2).each(function ([a, b]) {
  // do whatever
})


Would be slightly less elegant without SpiderMonkey's JS extensions, but you get the idea.

EDIT: Actually never mind, that does something different, I misread your post.
~Radnen: code tag fix
  • Last Edit: January 16, 2014, 11:09:51 pm by Radnen

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Link.js v0.2.3
Reply #58
Mother****:
Code: (text) [Select]

Link map-filter-map-each: 0.1900000000023283ms
Lazy map-filter-map-each: 1.1200000000098953ms
Lo-Dash map-filter-map-each: 4.499999999970896ms
actual for loop: 0.18000000003667083ms


I did a test, not expecting this in the slightest. Jesus Christ. No wonder Jest can speed up his calculations in his game; it's just as good as native for-loop speed, if only slightly slower.

The timer is not that accurate, and sometimes they are the same time. It's not quitting early or anything - it's actually doing the full range of calculations!
  • Last Edit: January 19, 2014, 02:05:26 am by Radnen
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: [code] Link.js v0.2.3
Reply #59
It's a nice way to make run-time modification and redrawing of Majestic maps quite fast, and still very simple to read!

I would say that, if there are drawbacks of Link compared to Lazy or the like, Link is quite well suited to usage in Sphere.