Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 8 of 8
  1. #1
    Regular Coder
    Join Date
    Jan 2004
    Location
    USA
    Posts
    364
    Thanks
    12
    Thanked 6 Times in 6 Posts

    Best way to map multiples values to a pair of values

    Hi,
    What's a good way/ideal data structure to achieve this?

    The objective of the code/function is to map user-inputted strings into a pair of specific, hard-coded strings. For example, say the user types "firefox" or "ff", or "fx". The output would be the pair ["browser", "mozilla"], for example.

    I'm currently using a multidimensional array, but it feels inefficient and I'm having trouble mapping an arbitrary number of inputs into 2 outputs.

    Code:
    var strings = [ ["input1", "output1a"],
                    ["input2", "output1a"],
                    ["input3", "output1a"],
                    ["input1", "output1b"],
                    ["input2", "output1b"],
                    ["input3", "output1b"]
                  ];
    How should I map the elements ["input1", "input2", "input3"] => ["output1a", "output1b"] ?

    Another method I used previously was a massive switch statement. This fulfills my needs, but I'm not sure about the efficiency (though if I remember correctly, switch statements become more efficient as size grows, since it uses a hash table?).

    Code:
    switch (input) {
        case "ff": case "firefox": case "fx" : case "ffox":
            return ["browser", "mozilla"];
        case "ie": case "internet explorer":
            return ["browser", "microsoft"];
        ...
    }
    Last edited by qwertyuiop; 12-24-2011 at 04:58 AM. Reason: added example
    Running Windows 7 x64

  • #2
    Regular Coder Apothem's Avatar
    Join Date
    Mar 2008
    Posts
    380
    Thanks
    36
    Thanked 25 Times in 25 Posts
    You can use OOP in it:

    var f = {"foo" : "bar"};
    document.write(f.foo);
    document.write(f["foo"]); // essentially, OOP is just an array...

  • #3
    Regular Coder
    Join Date
    Jan 2004
    Location
    USA
    Posts
    364
    Thanks
    12
    Thanked 6 Times in 6 Posts
    Quote Originally Posted by Apothem View Post
    You can use OOP in it:

    var f = {"foo" : "bar"};
    document.write(f.foo);
    document.write(f["foo"]); // essentially, OOP is just an array...
    Thanks Apothem, but I don't see how this would be more efficient? Could you elaborate?

    I was looking at my code some more, and here's what I have as of now:

    Code:
    var strings = [
                   [["input1","input2","input3"], "output1a", "output1b"],
                   [["input4","input5","input6"], "output2a", "output2b"]
                  ];
    Seems to work fine for now
    Running Windows 7 x64

  • #4
    Regular Coder Apothem's Avatar
    Join Date
    Mar 2008
    Posts
    380
    Thanks
    36
    Thanked 25 Times in 25 Posts
    Oooh wait my bad, I thought you wanted some sort of associative array. What you want is some sort of Graph then.

    Here's how a Graph can work (though it is more complicated than this):
    Code:
    function Graph() {
      var nodes = {};
      this.add = function(n, m) {
        for(var i = 0; i < n.length; i++) {
          nodes[n[i]] = m;
        }
      };
    
      this.get = function(n) {
        return nodes[n];
      };
    }
    
    g = new Graph();
    g.add(["foo", "bar", "baz"], "quz"); // "quz" can be ["quza", "quzb"] if you wanted
    document.write(g.get("bar"));
    document.write(g.get("baz"));
    Now, in reality a graph should have real nodes and have a union + find method. Seeing as you probably want things simple, this is how you would do it (though you can alter it to be better). It would take O(n) time to add the "inputs" and O(1) time to receive it. Though it may be the case that it takes more memory (though the memory taken is very small [a few bytes] and negligible).

    As far as efficiency may go, again a Node class might make things more efficient. What you can then do is union one node to another, then use a find() operation to get where the node is pointing to (to be specific, a union by height + path compression). This is not a needed solution unless your JS program is extremely big with lots of inputs that map to outputs (and by extremely big, I mean thousands).
    Last edited by Apothem; 12-24-2011 at 07:33 AM.

  • #5
    Regular Coder
    Join Date
    Jan 2004
    Location
    USA
    Posts
    364
    Thanks
    12
    Thanked 6 Times in 6 Posts
    That's pretty neat. Thanks Apothem!

    So I think I see where your current Graph() isn't very memory-optimized. When you assign multiple inputs to the same output, each output is essentially a separate piece of data in memory, is that right? I don't understand what you mean by union, how would I modify this with a node class?
    Running Windows 7 x64

  • #6
    Regular Coder Apothem's Avatar
    Join Date
    Mar 2008
    Posts
    380
    Thanks
    36
    Thanked 25 Times in 25 Posts
    Well again, memory shouldn't be an issue - including if your JS is small. As a result, the solution I have given works fairly well. If you had a large scale program that had similar functionality and is more intensive on the server, that is when you worry about things like memory.

    Explaining an optimal graph is quite a bit difficult, and you would probably hear better explanations online or from real professors. Essentially what happens is that you have nodes that contain a pointer (if you don't know what a pointer is, you should probably stop reading here) to another node. You can then create an edge (or union) two nodes together (which means you're making node x have a pointer to node y).

    Well, suppose that node y is pointing to node z, and node z to node f. And suppose further that node f has key "foobar". Then if you use a find() on whatever value node x has, you will be given back node f (and if you do path compression, you would make all of x, y, and z point to f). From there, you would just get the key value of node f.

    Such a graph would definitely take less memory than the method I have written for you, but it is also more complex and unneeded. JavaScript programs can be made quite simply and generally do not need such optimization because the language is run by the client, not by some server. More over, the amount of memory used is minimal and the speed of the program is of microseconds - meaning that if you were to implement a more advanced, optimized solution the clients will not even notice it. As such worrying over such trivial things is not worth your time.
    Last edited by Apothem; 12-25-2011 at 09:46 AM.

  • #7
    Regular Coder
    Join Date
    Jan 2004
    Location
    USA
    Posts
    364
    Thanks
    12
    Thanked 6 Times in 6 Posts
    Apothem, you're probably right. While there will be some data duplication, I wouldn't be saving very much memory, relative so the unique data set. Thanks again, though out of curiosity, what approach would this need? I understand pointers from C and C++, but I haven't learned JS formally enough to know how to implement this.
    Running Windows 7 x64

  • #8
    Regular Coder Apothem's Avatar
    Join Date
    Mar 2008
    Posts
    380
    Thanks
    36
    Thanked 25 Times in 25 Posts
    I believe most things in C++ can be related to in JavaScript. You would simply need a Graph class and a Node class. A node would probably have an edgeTo list and also a key. Your Graph would simply add a node of each string you have. Suppose you have the following nodes:
    billy
    bob
    joe
    man
    jane
    rose
    woman

    And you have a Graph g. You would then do something as such:
    g.union(joe, man); // joe now has an edge to man
    g.union(bob, joe); // bob has edge to joe
    g.union(billy, joe); // billy has edge to joe
    g.find("billy"); // returns man
    g.union(rose, woman); // rose has edge to woman
    g.union(jane, woman); // jane has edge to woman
    g.find("jane"); // returns woman
    g.union(woman, man); // edge from woman to man
    g.find("jane"); // returns man
    g.find("bob"); // returns man


    Now suppose you want the node to have more than one key. Then instead of having the key as a string, make it a vector/array. Or you can add in another key and have something like getType and getName. In real graph, though, you can technically have more than one edge from one node to another (e.g. node x can have an edge to node y and node z). I will not go further than that, though you can probably assume what happens with such a system.

  • Users who have thanked Apothem for this post:

    qwertyuiop (12-25-2011)


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •