Ускорение процесса сбора подслов, которые вы можете записать с помощью символов других слов - PullRequest
Новая
       5

Ускорение процесса сбора подслов, которые вы можете записать с помощью символов других слов

0 голосов
/ 28 сентября 2019

Цель этого кода - вывести список массивов, содержащих слова объекта длины его индекса, который также содержит массив массивов подслов, которые также содержат подслова длины его индекса.Эти подслов являются словами, которые вы можете записать с помощью символов самого слова.Я пытаюсь оптимизировать свой код, чтобы он мог обрабатывать около 81 000 слов с большей скоростью.Текущая программа запускается и завершит процесс, но это займет несколько часов.Я изо всех сил пытаюсь найти, где в моем коде может быть изменено лучше, чтобы уменьшить время, необходимое для запуска.

Это пример файла words.txt. 

do
dog
eat
go
god
goo
good
tea

Ниже приведены ожидаемые подсловВыходные данные .json из вышеуказанного txt-файла. 

[
    [],
    [],
    [
        {
            "word": "do",
            "subwords": [
                [],
                [],
                []
            ]
        },
        {
            "word": "go",
            "subwords": [
                [],
                [],
                []
            ]
        }
    ],
    [
        {
            "word": "dog",
            "subwords": [
                [],
                [],
                [
                    "do",
                    "go"
                ],
                [
                    "god"
                ]
            ]
        },
        {
            "word": "eat",
            "subwords": [
                [],
                [],
                [],
                [
                    "tea"
                ]
            ]
        },
        {
            "word": "god",
            "subwords": [
                [],
                [],
                [
                    "do",
                    "go"
                ],
                [
                    "dog"
                ]
            ]
        },
        {
            "word": "goo",
            "subwords": [
                [],
                [],
                [
                    "go"
                ],
                []
            ]
        },
        {
            "word": "tea",
            "subwords": [
                [],
                [],
                [],
                [
                    "eat"
                ]
            ]
        }
    ]
]

Ниже приведен код, выполняющий вызов слова words.txt и вывод subwords.json 

const fs = require('fs')

const totalTalkText = fs.readFileSync('words.txt').toString()

const sortedWords = totalTalkText
  .toLowerCase()
  .split(/[^a-zA-Z]+/g)
  .sort()
  .sort((a, b) => {
    return a.length - b.length
  })

const finalData = new Array()

for (i = 0; i < sortedWords[0].length; i++) {
  finalData[i] = []
}

sortedWords.forEach((word, index) => {
  const subwordsArray = new Array()
  let wordObject = {
    word: word
  }

  if (finalData.indexOf(word.length) === -1) {
    finalData[word.length] = new Array()
  }

  sortedWords.some(subword => {
    if (subword.length > word.length) return

    if (subwordsArray.indexOf(subword.length) === -1) {
      subwordsArray[subword.length] = new Array()

      for (i = 0; i < sortedWords[0].length; i++) {
        subwordsArray[i] = []
      }
    }

    if (subword !== '' && word !== subword && isSubword(word, subword)) {
      subwordsArray[subword.length].push(subword)
    }
  })

  wordObject.subwords = subwordsArray

  finalData[word.length].push(wordObject)
  //console.log(`${word}: ${index / 814.88}%`) //This is mostly to help me gauge how long the program would take
})

fs.writeFileSync('subwords.json', JSON.stringify([...finalData]))

function isSubword(word, subword) {
  let tmpArray = new Array(256)

  for (let i = 0; i < 256; i++) tmpArray[i] = 0

  for (let i in word) tmpArray[word.charCodeAt(i)] += 1

  for (let i in subword) {
    tmpArray[subword.charCodeAt(i)] -= 1
    if (tmpArray[subword.charCodeAt(i)] < 0) return false
  }
  return true
}

Я пыталсячтобы найти лучший способ проверить, является ли слово подсловом в функции isSubword, но не имело успеха.Опять же, код должен работать в течение длительного периода времени, я просто пытаюсь заставить его работать значительно быстрее.Любая помощь будет принята с благодарностью!

1 Ответ

0 голосов
/ 28 сентября 2019

Только для функции isSubword, я думаю, вы могли бы ускорить процесс, используя цикл while (который можно прерывать) вместо циклов for (который всегда будет выполняться заданное количество раз).Вот пример, где мы разбиваем слово и подслово на массив символов, а затем в цикле while мы проверяем, есть ли каждый символ подслова в слове, а затем удаляем его из массива слов, если он есть.Как видно из журнала консоли, цикл while прекратит итерацию, если найдет символ, который не содержится в слове. 

function isSubword(word, subword) {
  const wordArray = word.split("");
  const subwordArray = subword.split("");
  let isSubword = true;
  let i = 0;
  while(i < subwordArray.length && isSubword){
    const matchIndex = wordArray.findIndex(l => l === subwordArray[i] );
    console.log(subwordArray[i]);
    if(matchIndex < 0){
      isSubword = false;
    } else {
      wordArray.splice(matchIndex, 1);
      i += 1;
    }
  }
  return isSubword;
}

console.log(isSubword('test', 'set'));
console.log(isSubword('test', 'if'));
console.log(isSubword('test', 'tt'));
console.log(isSubword('test', 'ttt'));
...