代码之家 › 专栏 › 技术社区 › j_d

提高了这种组合算法的性能?

permutation combinations performance algorithm javascript

j_d · 技术社区 · 7 年前

我正在努力 this kata 从暗战中。任务是:

给定一个特定的数字,你能用它的数字得到多少个三的倍数?

相信你有362号。可以从中生成的数字是:

362 ----> 3, 6, 2, 36, 63, 62, 26, 32, 23, 236, 263, 326, 362, 623, 632

我编写了以下递归函数来计算所有可能性:

const findMult_3 = (num) => {

  const powerset = (set) => {
    const combinations = []
    const combine = (prefix, chars) => {
      for (let i = 0; i < chars.length; i++) {
        const newPrefix = parseInt(prefix + chars[i])
        if (!combinations.includes(newPrefix)) {
          combinations.push(newPrefix)
        } else {
          console.log('encountered duplicate')
        }
        combine(newPrefix, chars.filter((x, ind) => ind !== i))
      }
    }
    combine('', set)
    return combinations.sort((a, b) => a - b)
  }

  const allCombinations = powerset(num.toString().split(''))
  const factorsOfThree = allCombinations.filter(x => x % 3 === 0).filter(x => x !== 0)

  return [factorsOfThree.length, factorsOfThree.pop()]

}

findMult_3(43522283000229)

我很早就注意到有人碰到我很多重复的案例,因此 console.log('encountered duplicate') 旗帜。

这个算法的执行对于大量的数据来说要花很长的时间,例如 43522283000229 .

如何提高此代码的性能,或者应该完全废弃它?

2 回复 | 直到 7 年前

meriton 7 年前

对于大多数编码katas,算法的选择远比实现细节重要,但是在我们开始之前,让我指出实现中最明显的缺陷:

    if (!combinations.includes(newPrefix)) {
      combinations.push(newPrefix)
    } else {
      console.log('encountered duplicate')
    }
    combine(newPrefix, chars.filter((x, ind) => ind !== i))

combinations 是一个数组,并且 includes 通过迭代数组并检查每个元素来工作。也就是说,要检查某个元素是否重复,需要将其与以前遇到的每个组合进行比较。因为有很多这样的指数,这将是非常缓慢的。如果您使用dictionary对象或 Map 相反,你的代码会快得多。

另外,您是否注意到正在继续生成组合,即使组合是重复的?那是多余的。

因此,廉价的改进将是:

const combinations = {};
if (combinations[prefix]) {
  // duplicate, do nothing
} else {
  combinations[prefix] = true;
  combine(...);
}

然而,真正的改进是选择更好的算法。如果你利用了这个问题的数学结构,你就可以找到解的数目而不必全部迭代。

以下见解可能会有所帮助:

一个数可以被三个当且仅当其位数之和是。
当且仅当被3除后的余数之和为0时,数字之和可被3除。
输入中的数字顺序无关紧要

Danny_ds 7 年前

一个(第一个)优化是只检查或生成 数字和可被3整除 ,因为只有这些数字可以被3整除。

所以在你的例子中( 362 )你可以跳过所有的组合 3 and 2 , 6 and 2 以及所有可能与3位数的组合(因为3位数的和不能被3整除)。

对于较大的数字( 43522283000229 )你可以跳过更多,例如所有数字组合:

43, 35, 52, ...
435, 352, .., 283, ...
4352 (thus, including all possible combinations of those 4 digits), ...
43522, ...
43528, 43529, ...
43528309, ...
and so on

可能的算法 :

Original number:        43522283000229

First, sort the digits: 00022222334589

Then find all distinct combinations of digits where
their sum is a multiple of 3:

left to right:

1 digit : 3, 9
2 digits: 03, 09, 24, 33, 39, 45, 48, ...
3 digits: 003, 009, 024, 033, 039, 222, 234, ...
n digits ...

Now, for all above numbers create every possible combination with their
digits, skip those with leading zeros.:

3, 9, 30, 90, 24, 42, 33, 39, 93, 45, 54, 48, 84, 300, 900,
204, 240, 402, 420, 309, 390, 903, 930, 222, 234, 243, ...

We don't have to check for division by 3, they all match.
We don't have to check for duplicates.

You could then sort the resulting list if needed.