2

for example, Suppose I have a 2d array:

let filterArr=[
  [1,1,0,1,1],
  [0,1,1,1,0],
  [1,1,0,1,0]
];

I want to find and store the index of column that all are 1, i.e.:position 1 and 3, and the codes are the following:

Use Array:

let filterArr=[
  [1,1,0,1,1],
  [0,1,1,1,0],
  [1,1,0,1,0]
];

let results=[];
for(let i=0;i<filterArr[0].length;i++){
  let isAllOne=true;
  for(let filter of filterArr){
    if(filter[i]!=1){
      isAllOne=false;
      break;
    }
  }
  if(isAllOne){
    results.push(i);
  }
}
//store results for other use

Use Set:

let filterArr=[
  [1,1,0,1,1],
  [0,1,1,1,0],
  [1,1,0,1,0]
];

let results=new Set();
for(let i=0;i<filterArr[0].length;i++){
  let isAllOne=true;
  for(let filter of filterArr){
    if(filter[i]!=1){
      isAllOne=false;
      break;
    }
  }
  if(isAllOne){
    results.insert(i);
  }
}
//store results for other use

Which I found "results" can be either Array or Set. My question is, not limited to this case, if I found both Array and Set can finish my task, should I use Array or Set?

  • 2
    Both Array and Set has equivalent complexity for insert operations which is O(1): constant. So it depends on what you are planning to do with the result collection... – Arcones Oct 4 '18 at 6:56
  • How are you going to be using results? Are you going to do set-like things, such as checking if a value is an element of that set, or are you only going to do collection like things, such as looping (or maping) over each value? – Caleth Oct 4 '18 at 8:17
  • My own rule of thumb, always List if I return something supposed to be only read even if they're unique because a set is way heavier (time, memory) to build (at least an HastSet and even an identityset will be heavier than a default List based on simple Array implementation). So I use only Set when I'm sure that not only my results are unique, but also that this collection may be written and I need to ensure the uniqueness. An example : when transforming a list to a map of <key,list<value>> in the old school way, I use a set for the keys. – Walfrat Oct 4 '18 at 11:55
6

The use of either Array or Set by your function is equivalent: You create a container, and you push stuff into it. This leaves two areas for consideration:

  1. What does the consumer need to do with the container?

  2. Which container is more efficient (space or time)?

If you find that the consumer just iterates over the container, both Array and Set are equivalent again from this usage perspective. However, if your user needs to answer the question "is this index in the container?", then Set is the only appropriate container type.

Once you have asserted that the container type is indeed irrelevant to use, both on the producer and consumer side, go for the more efficient container:

  • Array should be implemented as a simple slap of contiguous memory that holds (the references to) its elements. A push() generally means 1) checking for space (one comparison), 2) appending the new element to the end of the buffer, and 3) updating the length field.

  • Set is required to ensure that its elements are unique. That is, where Array.push() is happy to push an element twice, Set.insert() must somehow catch this condition and handle it. This requires extra work. To get O(1) performance, Set would normally be implemented as a hash table. Hash tables are fast, but they are definitely more complex than a simple, contiguous buffer. Thus, Set.insert() will generally have to do significantly more work than Array.push(), and its data structures are very likely to consume more memory.

Both space and time efficiency are better for Array than for Set. And this is why I would default to using Array over Set whenever their use is equivalent.

2

From what you have shown in your question, it does not matter (and consider to refactor your code in case it starts to matter).

not limited to this case, if I found both Array and Set can finish my task, should I use Array or Set

Producing an Array or a Set is typically not an end in itself, it is a means to an end, so often you can find out what the caller of your method which produces this result might prefer.

Note, if you start using an array, and it turns out for further processing a Set would be beneficial (or you need both, the array and the set representation), you can easily convert it:

  let resultSet = new Set(results)

I am not a Javascript expert, but I would expect the conversion the other way round to require at a little bit more code. Thus, if in doubt, I personally would start with an array first, and switch to a set if it fits better, but that is somewhat opinionated.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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