检查数字内数字范围而不重复的最有效方法

2022-01-17 00:00:00 algorithm numbers javascript

给定一个数字 n ，一个最小数字 min ，一个最大数字 max ，什么是最有效的确定方法

  1. 数字 n 是否在范围内，包括 min - max

  2. 数字 n 是否包含重复的数字

  3. 这里的效率意味着方法或方法集需要最少的计算资源，并在最少的时间内返回 true 或 false

  4. 上下文:for 循环中 if 的条件，可能需要数千到数十万次迭代才能返回结果；其中返回 true 或 false 对于 Number 检查所需的毫秒数可能会影响性能

在 DevTools 的 Profiles 面板上，对 71,3307 项迭代的集合，列出了以下 RegExp使用 27.2ms 的总 1097.3ms 来完成循环.在 836,7628 个项目的集合中，迭代 RegExp 下面使用了 193.5ms，总共 11285.3ms .p>

要求:在最短的时间内返回上述参数的 Boolean true 或 false 的最有效方法.

注意:解决方案不必局限于 RegExp ；下面用作返回预期结果的模式.

<小时>

当前 js 利用 RegExp re , RegExp.protype.test() 

var min = 2, 最大值 = 7, re = new RegExp("[" + min + "-" + max + "](.)(?!=1)", "g"), arr = [81, 35, 22, 45, 49];for (var i = 0; i < arr.length; i++) {console.log(re.test(arr[i]), i, arr[i])/*假 0 81真实 1 35假 2 22真实 3 45假 4 49*/}

解决方案

关联数组方法:

这具有易于理解的优点.

函数 checkDigits(min, max, n) {var 数字 = 数组(10)；//声明数组的长度(10 位)以避免任何进一步的内存分配而(n){d = (n % 10);//获取最后一个数字n = n/10 >>0;//从我们的数字中删除它(>>0 位等价于 compose(Math.floor, Math.abs))if (d < min || d > max || digits[d])//测试d"是否超出范围或是否已在digits"数组中检查返回假；别的数字[d] = 真；//将数字标记为存在}}

var min = 2, 最大值 = 7, arr = [81, 35, 22, 45, 49];函数 checkDigits(min, max, n) {var 数字 = 数组(10)；//声明数组的长度(10 位)以避免任何进一步的内存分配而(n){d = (n % 10);//获取最后一个数字n = n/10 >>0;//从我们的数字中删除它(>>0 位等价于 compose(Math.floor, Math.abs))if (d < min || d > max || digits[d])//测试d"是否超出范围或是否已在digits"数组中检查返回假；别的数字[d] = 真；//将数字标记为存在}返回真；}for (var i = 0; i < arr.length; i++) {console.log(checkDigits(min, max, arr[i]), i, arr[i])}

二进制掩码方法:

这会将数组替换为实际上用作位数组的整数.它应该更快.

函数 checkDigits(min, max, n) {可变数字 = 0;而(n){d = (n % 10);n = n/10 >>0;if (d < min || d > max || (数字 & (1 << d)))返回假；别的数字 |= 1 <<d;}返回真；}

function checkDigits(min, max, n) {可变数字 = 0;而(n){d = (n % 10);n = n/10 >>0;if (d < min || d > max || (数字 & (1 << d)))返回假；别的数字 |= 1 <<d;}返回真；}

二进制掩码方法说明:

<代码>1 <<d 创建一个 位掩码，一个整数，其中 d 位设置，所有其他位设置为 0.
数字 |= 1 <<d 在整数 digits 上设置由我们的位掩码标记的位.
数字&(1 << d) 将我们的位掩码标记的位与 digits(先前标记位的集合)进行比较.
如果需要，请参阅 位运算符 上的文档详细了解这一点.

所以，如果我们检查 626，我们的数字会是这样的:

________n_____626_______________|d |6面具 |0001000000数字 |0000000000|___n_____62________________|d |2面具 |0000000100数字 |0001000000|___n_____6___|d |6面具 |0001000000数字 |0001000100^位已设置，返回 false

Given a number n , a minimum number min , a maximum number max , what is the most efficient method to determine

  1. Number n is or is not within range , inclusive of , min - max

  2. Number n does or does not contain duplicate numbers

  3. Efficiency meaning here that the method or set of methods requires the least amount of computational resources and returns either true or false in the least amount of time

  4. Context: Condition at if within a for loop which could require from thousands to hundreds of thousands of iterations to return a result; where milliseconds required to return true or false as to Number check could affect performance

At Profiles panel at DevTools on a collection of 71,3307 items iterated, RegExp below was listed as using 27.2ms of total 1097.3ms to complete loop . At a collection of 836,7628 items iterated RegExp below used 193.5ms within total of 11285.3ms .

Requirement: Most efficient method to return Boolean true or false given above parameters , within the least amount of time.

Note: Solution does not have to be limited to RegExp ; used below as the pattern returned expected results.

Current js utilizing RegExp re , RegExp.protype.test() 

var min = 2
, max = 7
, re = new RegExp("[" + min + "-" + max + "](.)(?!=1)", "g")
, arr = [81, 35, 22, 45, 49];

for (var i = 0; i < arr.length; i++) {
  console.log(re.test(arr[i]), i, arr[i])
    /*
      false 0 81 
      true 1 35
      false 2 22
      true 3 45
      false 4 49 
    */
}

解决方案

Associative arrays approach:

This has the advantage of being easily understandable.

function checkDigits(min, max, n) {
    var digits = Array(10);                   // Declare the length of the array (the 10 digits) to avoid any further memory allocation
    while (n) {
        d = (n % 10);                         // Get last digit
        n = n / 10 >>0;                       // Remove it from our number (the >>0 bit is equivalent to compose(Math.floor, Math.abs))
        if (d < min || d > max || digits[d])  // Test if "d" is outside the range or if it has been checked in the "digits" array
            return false;
        else
            digits[d] = true;                 // Mark the digit as existing
    }
}


var min = 2
, max = 7
, arr = [81, 35, 22, 45, 49];

function checkDigits(min, max, n) {
    var digits = Array(10);                   // Declare the length of the array (the 10 digits) to avoid any further memory allocation
    while (n) {
        d = (n % 10);                         // Get last digit
        n = n / 10 >>0;                       // Remove it from our number (the >>0 bit is equivalent to compose(Math.floor, Math.abs))
        if (d < min || d > max || digits[d])  // Test if "d" is outside the range or if it has been checked in the "digits" array
            return false;
        else
            digits[d] = true;                 // Mark the digit as existing
    }
    return true;
}

for (var i = 0; i < arr.length; i++) {
  console.log(checkDigits(min, max, arr[i]), i, arr[i])
}

Binary mask approach:

This replaces the Array with an integer that is in effect used as an array of bits. It should be faster.

function checkDigits(min, max, n) {
    var digits = 0;                   
    while (n) {
        d = (n % 10);                         
        n = n / 10 >>0;
        if (d < min || d > max || (digits & (1 << d)))
            return false;
        else
            digits |= 1 << d;
    }
    return true;
}


function checkDigits(min, max, n) {
    var digits = 0;                   
    while (n) {
        d = (n % 10);                         
        n = n / 10 >>0;
        if (d < min || d > max || (digits & (1 << d)))
            return false;
        else
			digits |= 1 << d;
    }
    return true;
}

Explanation for binary mask approach:

1 << d creates a bit mask, an integer with the d bit set and all other bits set to 0.
digits |= 1 << d sets the bit marked by our bit mask on the integer digits.
digits & (1 << d) compares the bit marked by our bit mask with digits, the collection of previously marked bits.
See the docs on bitwise operators if you want to understand this in detail.

So, if we were to check 626, our numbers would go like this:

________n_____626_______________
           |
        d  |  6
     mask  |  0001000000
   digits  |  0000000000
           |
________n_____62________________
           |
        d  |  2
     mask  |  0000000100
   digits  |  0001000000
           |
________n_____6_________________
           |
        d  |  6
     mask  |  0001000000
   digits  |  0001000100
                 ^
               bit was already set, return false

相关文章