3
\$\begingroup\$

I am implementing a binary search to retrieve all matches of a specified value. Instead of a regular binary search that would just return the first match, I want to get that first match AND all matches above and below it in the set of objects.

For example, I have an array of objects that are sorted by the name property of each object in alphabetical order, and the first letter of that name property is what I use for comparison of the value provided.

The object would look like this (using fake values):

[
    { name: 'Apple',      id: 1, ...},
    { name: 'Apple',      id: 2, ...},
    { name: 'Basketball', id: 3, ...},
    { name: 'Basketball', id: 4, ...},
    { name: 'Cooking',    id: 5, ...},
    { name: 'Cooking',    id: 6, ...},
    { name: 'Dinosaurs',  id: 7, ...},
    ...
]

The list goes on all the way to Z, and each set of letters has probably 100+ results so there is a big set of objects here.

My code achieves what I want, but I feel as though I wrote way more code than I needed, but I've already refactored a few times and can't seem to shrink it much more.

A simple for loop could have achieved this for me and shrunk the code down to like 10 lines, but it would be essentially looping through a set of 2000+ items even when it only needs the first 100..

Here's the code (the main function is _binarySearchAll at the bottom):

getBrands(letter) {
    let brands = this.brands,
        _firstLetter = brand => {
            if ('hasOwnProperty' in brand && brand.hasOwnProperty('name')) {
                return brand.name.slice(0, 1).toLowerCase();
            }

            return false;
        },
        _traverse = (up, arr, i) => {
            let store = [],
                direction = up ? 1 : -1;

            while (_firstLetter(arr[i]) === letter) {
                store.push(arr[i]);

                i = i + direction;

                if (typeof arr[i] === 'undefined') {
                    break;
                }
            }

            return store;
        },
        _each = (arr, callback) => {
            let i = 0,
                len = arr.length - 1;

            while (++i < len) {
                callback(arr[i]);
            }
        },
        _compare = (brand, letter) => {
            let brandLetter = _firstLetter(brand);

            if (brandLetter === letter) {
                return 0;
            } else if (brandLetter < letter) {
                return 1;
            } else if (brandLetter > letter) {
                return -1;
            }
        },
        _all = (arr, i) => {
            let store = [],
                down = false,
                up = true;

            _each(_traverse(down, arr, i - 1), match => {
                store.push(match);
            });

            _each(_traverse(up, arr, i + 1), match => {
                store.push(match);
            });

            store.push(arr[i]);

            return store;
        },
        _binarySearchAll = (arr, val, compare) => {
            let start = 0,
                stop = arr.length - 1,
                mid = (start + stop) >> 1;

            while (start < stop) {
                let result = compare(arr[mid], val);

                if (result === 0) {
                    return _all(arr, mid);
                } else if (result > 0) {
                    start = mid + 1;
                } else if (result < 0) {
                    stop = mid - 1;
                }

                mid = (start + stop) >> 1;
            }
        };

    return _binarySearchAll(brands, letter, _compare);
}

Any help would be appreciated. If you want to test out the function, copy and paste it into Chrome Dev tools (or any other JS playground that supports ES6) and just past a similar array of objects as provided in my example. Try to have like 20 of each letter, then call getBrands('a') or some other letter, and you'll get an array of objects all starting with the first letter 'a'.

\$\endgroup\$
  • \$\begingroup\$ Just to be clear, the goal here is to reduce code size, not result size, right? \$\endgroup\$ – Pimgd Aug 2 '16 at 13:03
  • 2
    \$\begingroup\$ Correct. The code works just as I want it to. I just feel like implementing a speed optimization shouldn't turn the code from 15 lines of code to like 100 which is what it is now. \$\endgroup\$ – Lansana Aug 2 '16 at 13:17
  • \$\begingroup\$ I question the data structure that you propose here. Perhaps a doubly-linked list would be most appropriate. \$\endgroup\$ – Mike Brant Aug 2 '16 at 15:34
1
\$\begingroup\$

Unless I wrongly understood your question (like if you want to use binary search), it seems you merely look for the fastest solution.

I was curious to try with what I found the simplest method, using a filter:

function getBrandsSimple(letter) {
  return brands.filter( item => item.name.charAt(0).toLowerCase() == letter);
}

Then I created a big array of 3000 items from 15 brands with 200 ids each, and tested your solution getBrands against the simple one above getBrandsSimple.
The results are:

  • not surprisingly the time needed by getBrands differ considerably depending on the choosen letter (and also depending on the array order, see below)
  • obviously, at the opposite the time needed by getBrandsSimple is rather constant
  • in the worst case I noticed, getBrandsSimple needs less than 2x the time needed by getBrands
  • in other cases, getBrands may need till 4x the time needed by getBrandsSimple

In additon, getBrands often returns wrong results.
From the definition of my test array, each case should return exactly 200 items, while getBrands frequently returns only 196 items, and sometimes only 1.

Moreover, I added an option to shuffle the array: then getBrands returns most often only 1 result or no result at all (undefined)!
I didn't dive into your code to look for what turns wrong.

You may check all that using this snippet:

var brandsList = [
      'Apple',
      'Basketball',
      'Cooking',
      'Dinosaurs',
      'ES6',
      'Features',
      'Golf',
      'Highlighting',
      'Informatics',
      'JSON',
      'KiloBytes',
      'Lambda',
      'More...',
      'Nothing',
      'Original',
    ],
    filler = new Array(200).fill(''),
    brands = brandsList.reduce( (result, brandName) =>
      result.concat(
        filler.map((item, index) => {
          return {name: brandName, id: index + 1};
        })
      )
    , []);

getBrandsSimple = function(letter) {
  return brands.filter( item => item.name.charAt(0).toLowerCase() == letter);
}

getBrands = function(letter) {
    let brands = this.brands,
        _firstLetter = brand => {
            if ('hasOwnProperty' in brand && brand.hasOwnProperty('name')) {
                return brand.name.slice(0, 1).toLowerCase();
            }
            return false;
        },
        _traverse = (up, arr, i) => {
            let store = [],
                direction = up ? 1 : -1;
            while (_firstLetter(arr[i]) === letter) {
                store.push(arr[i]);
                i = i + direction;
                if (typeof arr[i] === 'undefined') {
                    break;
                }
            }
            return store;
        },
        _each = (arr, callback) => {
            let i = 0,
                len = arr.length - 1;
            while (++i < len) {
                callback(arr[i]);
            }
        },
        _compare = (brand, letter) => {
            let brandLetter = _firstLetter(brand);
            if (brandLetter === letter) {
                return 0;
            } else if (brandLetter < letter) {
                return 1;
            } else if (brandLetter > letter) {
                return -1;
            }
        },
        _all = (arr, i) => {
            let store = [],
                down = false,
                up = true;
            _each(_traverse(down, arr, i - 1), match => {
                store.push(match);
            });
            _each(_traverse(up, arr, i + 1), match => {
                store.push(match);
            });
            store.push(arr[i]);
            return store;
        },
        _binarySearchAll = (arr, val, compare) => {
            let start = 0,
                stop = arr.length - 1,
                mid = (start + stop) >> 1;
            while (start < stop) {
                let result = compare(arr[mid], val);
                if (result === 0) {
                    return _all(arr, mid);
                } else if (result > 0) {
                    start = mid + 1;
                } else if (result < 0) {
                    stop = mid - 1;
                }
                mid = (start + stop) >> 1;
            }
        };
    return _binarySearchAll(brands, letter, _compare);
}

function exec(funcName, func, letter) {
  console.time(funcName);
  result = func(letter);
  console.timeEnd(funcName);
  if (result) {
    // console.log(result.length + ' items:', result);
    console.log(result.length + ' items');
  } else {
    console.log(result);
  }
}

function shuffle(a) { // (thanks to http://stackoverflow.com/a/6274381/3415269)
    var j, x, i;
    for (i = a.length; i; i--) {
        j = Math.floor(Math.random() * i);
        x = a[i - 1];
        a[i - 1] = a[j];
        a[j] = x;
    }
}

var letter = prompt('Enter a letter', 'j');
if (confirm('Shuffle the brands array?')) {
  shuffle(brands);
}
exec('getBrands', getBrands, letter);
exec('getBrandsSimple', getBrandsSimple, letter);

\$\endgroup\$
  • \$\begingroup\$ If the code is about a binary search and you shuffle the array, isn't that expected to fail? Because binary search by definition needs a sorted list? \$\endgroup\$ – ChatterOne Aug 3 '16 at 7:21
  • \$\begingroup\$ @ChatterOne Uh... indeed, you're right! I stupidly didn't pay attention to that :) So finally the OP's solution seems even more weird: while he's looking for performance he uses a slow method which also needs taking time to sort the source previously! \$\endgroup\$ – cFreed Aug 3 '16 at 9:03
  • \$\begingroup\$ @cFreed I actually never sort in my code, the array of objects come sorted and ready to go. Your answer shows a different way of thinking that I didn't look into, and it actually shows some speed tests (I need to learn how to do this) so I don't just assume my code is faster when it's not. \$\endgroup\$ – Lansana Aug 3 '16 at 15:32
  • \$\begingroup\$ @Lansana Well if the array comes sorted, sure it makes tend to benefit of that to use binary search. But from the tests, as you can see, the gain is very minor (max half a millisecond for 3000 items). So in my opinion it's not worth the trouble of a complex and heavy code. And don't forget that, for some reason, it currently doesn't return the whole selection! \$\endgroup\$ – cFreed Aug 3 '16 at 18:30
1
\$\begingroup\$

Given that you only want to obtain results by letter, just make a separate array indexed by letter. Something like:

addToIndex = (index, key, elt) => {
  if (index[key]) index[key].push(elt)
  else index[key] = [elt];
}
// Initialize the brands list, then:
const index = [];
brands.forEach(elt => addToIndex(index, firstLetter(elt), elt));

Then, when you want all the matches for the letter, just access index.letter.

\$\endgroup\$
  • \$\begingroup\$ This is also a really clean and readable solution. \$\endgroup\$ – Lansana Aug 3 '16 at 15:44
1
\$\begingroup\$

Modifying a bit @Justin's answer, you can use a hash to store the values and reference the first letter as the key:

var brands = [
      "Apple",
      "Basketball",
      "Cooking",
      "Dinosaurs",
      "ES6",
      "Features",
      "Golf",
      "Highlighting",
      "Informatics",
      "JSON",
      "KiloBytes",
      "Lambda",
      "More...",
      "Nothing",
      "Original",
    ];

var lookupObject = {};

brands.forEach(function(element) {
  var currentLetter = element.slice(0,1).toLowerCase();
  lookupObject[currentLetter] = lookupObject[currentLetter] || [];
  lookupObject[currentLetter].push(element);
});

console.log(lookupObject["a"]);

BUT keep in mind that if you have an index, a reference or whatever that is based on letters, you may have problems when encountering some characters.

For example, it's not that easy to determine that è and e are the same letter, or È and e.

This:

var t="è";
var u="e";

console.log(t.toLowerCase() === u.toLowerCase());

will give you false.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the disclaimer. I didn't think about this, but it also won't matter really because all of the letters will be in the regular alphabet. \$\endgroup\$ – Lansana Aug 3 '16 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.