View Full Version : Best way to map multiples values to a pair of values

12-24-2011, 05:50 AM
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.

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?).

switch (input) {
case "ff": case "firefox": case "fx" : case "ffox":
return ["browser", "mozilla"];
case "ie": case "internet explorer":
return ["browser", "microsoft"];

12-24-2011, 05:59 AM
You can use OOP in it:

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

12-24-2011, 06:52 AM
You can use OOP in it:

var f = {"foo" : "bar"};
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:

var strings = [
[["input1","input2","input3"], "output1a", "output1b"],
[["input4","input5","input6"], "output2a", "output2b"]

Seems to work fine for now

12-24-2011, 08:20 AM
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):

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

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).

12-25-2011, 09:51 AM
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?

12-25-2011, 10:43 AM
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.

12-25-2011, 10:59 AM
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.

12-25-2011, 11:19 AM
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:

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.