Оптимизация разбиения строки

292

22 января 2017, 16:53

Есть некий кусок кода, подгружающий строки из файла в коллекцию с уникальными значениями

var WORDS = new Set()
let file = fs.readFileSync('file.txt') // 1 500 000+ строк
// Прошло ~10 мс
let text = iconv.decode(file, 'windows-1251')
// Прошло ~100 мс
let list = text.split('\n')
// Прошло ~500 мс
let i = 0
while (list[i] != null) {
    // Быстрее, чем "WORDS = new Set(list)"
    WORDS.add(list[i++])
}
// Прошло ~1100 мс

Самые толстые части кода — разбиение по ячейкам и перебор. Возможно ли это оптимизировать?

UPD:
Делается всё ради того, что бы быстро искать значение в коллекции

WORDS.has('string') // true или false

Так что, если есть другие способы хранения и поиска уникальных значений, я за

Answer 1

Ну если без шуток, то у Вас происходит два обращения к одному и тому же элементу массива. Вот так будет точно быстрее -

let length = list.length;
for(var i = 0; i < length; i++){
    Worlds.add(list[i]);
}

А по поводу просто проверки на существование, тут сложно сказать без замеров. Set работает со всеми типами, что должно сделать его работу теоретически медленнее чем обычный объект, который является базовым типом для всего в js и использует в качестве ключа строку. Я о -

let hash = {};
hash[list[i]] = true;
console.log(hash['string']);

добавление в Set -

const CharFactory = { 
  count: 0, 
  getChar(){ 
    return 'some text' + this.count++; 
  }, 
  reset(){ 
    this.count = 0; 
  } 
}; 
 
const ITERATION = 1000000; 
 
const set = new Set(); 
 
console.time('add in Set'); 
for(let i = 0; i < ITERATION; i++){ 
  set.add(CharFactory.getChar()); 
} 
console.timeEnd('add in Set');

добавление в Object -

const CharFactory = { 
  count: 0, 
  getChar(){ 
    return 'some text' + this.count++; 
  }, 
  reset(){ 
    this.count = 0; 
  } 
}; 
 
const ITERATION = 1000000; 
 
const hash = {}; 
 
console.time('add in Object'); 
for(let i = 0; i < ITERATION; i++){ 
  hash[CharFactory.getChar()] = true; 
} 
console.timeEnd('add in Object');

проверка в Set -

const CharFactory = { 
  count: 0, 
  getChar(){ 
    return 'some text' + this.count++; 
  }, 
  reset(){ 
    this.count = 0; 
  } 
}; 
 
const ITERATION = 1000000; 
 
const set = new Set(); 
 
for(let i = 0; i < ITERATION; i++){ 
  set.add(CharFactory.getChar()); 
} 
 
CharFactory.reset(); 
 
console.time('has in Set'); 
for(let i = 0; i < ITERATION; i++){ 
  let isCharExistValid = set.has(CharFactory.getChar()); 
} 
console.timeEnd('has in Set');

проверка в Object -

const CharFactory = { 
  count: 0, 
  getChar(){ 
    return 'some text' + this.count++; 
  }, 
  reset(){ 
    this.count = 0; 
  } 
}; 
 
const ITERATION = 1000000; 
 
const hash = {}; 
 
for(let i = 0; i < ITERATION; i++){ 
  hash[CharFactory.getChar()] = true; 
} 
 
CharFactory.reset(); 
 
console.time('has in Object'); 
for(let i = 0; i < ITERATION; i++){ 
  let isCharExistValid = hash[CharFactory.getChar()]; 
} 
console.timeEnd('has in Object');

Хоть это и нужно тестировать именно в той ноде в которой вы работает, я все же не удержался и написал тесты для браузера.

Answer 2

Для производительности стоит делать только один проход по строке.

let WORDS = {}; 
 
let file = fs.readFileSync('file.txt') // 1 500 000+ строк 
 
let text = iconv.decode(file, 'windows-1251'); 
 
let len = text.length; 
let offset = 0; 
for (let i = 0; i < len; ++i) { 
  if ((text[i] == '\n' || text[i] == '\r') && offset != i) { 
    WORDS[text.substring(offset, i)] = true; 
    offset = i + 1; 
  } 
} 
if (offset != len - 1) { 
  WORDS[text.substring(offset, len)] = true; 
}