javascript - programmation, problèmes d'algorithme

Question

J'ai eu une question dans l'interview d'avant-hier. Veuillez utiliser js, python, java, c, c++ et d'autres langages pour calculer 10 milliards de données en 10 secondes, et (ne peut être complété qu'en 3 secondes). des nombres pairs avant les nombres impairs est le suivant 1, 2, 3, 4, 5 les résultats de sortie sont 2, 1, 4, 3, 6, 5. Question 2 : En plus du code de 1, les exigences ne sont pas .. .

我想大声告诉你 · Answer

Je ne comprends pas la première question. Cela signifie-t-il que 2 nombres forment une paire et que le nombre pair précède le nombre impair ?

La deuxième question est simple. Si vous ne pouvez pas utiliser de boucle, utilisez l'itération de tableau.

代言 · Answer

En parlant de ça php 的 foreach n’a pas d’importance (rires

Je pense que l'intention de l'intervieweur est de vous demander d'écrire une fonction récursive ? Eh bien, je suppose que oui.

PHP中文网 · Answer

J'ai eu une question d'entretien avant-hier
Veuillez utiliser des langages tels que js, python, java, c, c++ pour calculer 10 milliards de données en 10 secondes, et complétez-les (seulement dans les 3 secondes), les nombres pairs viennent avant les nombres impairs
Le format est le suivant
1, 2, 3, 4, 5
Le résultat de sortie est
2, 1, 4, 3, 6, 5,
Question 2 : En plus du code en 1, il Il est nécessaire que le mot-clé for while ne puisse pas être utilisé, à partir de Obtenir tous les nombres premiers sur 10 milliards (le temps ne peut pas dépasser 3 secondes)
Comment faire ?

Puisqu'il ne peut pas être utilisé pendant un certain temps

Alors les performances récursives ne suffisent pas. . . Mais j'en utilise encore. . For Performance

Il existe peut-être un moyen astucieux

. . . 100亿 La taille devrait être là. Je ne l'ai pas encore trouvé.

Code

10 milliards, c'est un peu gros, je vais d'abord en prendre 100 000

var n = 1000 * 1000; 
var test = new Array(n).fill(n).map((e, idx) => idx);

De cette façon, vous pouvez obtenir un tableau de nombres naturels d'une longueur de 100 000.

Capture d'écran 1

// 剔除第一个负数 
var zs = res001.slice(1); 

var is6x = n => n % 6 === 0; 


var isPrime = n => {
     let temp = Math.sqrt(n);  
     
     for(let i = 2; i <= temp; i++){
         if(n % i === 0){
             return false; 
         }
     }
     
     return true;  
}  


var lasts = zs.filter(is6x).reduce((acc, cur) => {
    let left = cur - 1, right = cur + 1; 
    if (isPrime(left)) acc.push(left); 
    if (isPrime(right)) acc.push(right); 
    
    return acc; 
}, []); 

console.log(lasts);

Capture d'écran deux

Je ne sais pas si c'est vrai...

Mais nous devons encore remettre les nombres premiers 1 2 3 5 de 小于 6 séparément. (Pas d'orthographe ici)

Performances

Respectez le code écrit ci-dessus

var isEven = n => n % 2 === 0; 


var is6x = n => n % 6 === 0; 

var isPrime = n => {
     let temp = Math.sqrt(n);  
     
     for(let i = 2; i <= temp; i++)
        if(n %i== 0){
            return false; 
        }
     return true;  
}  


function timeTest(n){
    var test = new Array(n).fill(n).map((e, idx) => idx); 
    var res001 = test.map((e, idx) => {
        if (isEven(e)){
            return e - 1; 
        } else {
            return e + 1; 
        }
    }); 
    var zs = res001.slice(1); 
    
    var lasts = zs.filter(is6x).reduce((acc, cur) => {
        let left = cur - 1, right = cur + 1; 
        if (isPrime(left)) acc.push(left); 
        if (isPrime(right)) acc.push(right); 
        
        return acc; 
    }, []); 
    
    return lasts; 
}

test

var n = 1000 * 10000; 

console.time('1000 万')
timeTest(n); 
console.timeEnd('1000 万');

1000 万 Le résultat est tel que montré sur la photo

Cela a pris 13,8 secondes. Il est impossible de terminer le volume de 13.8 秒不可能做到 10 + 3 秒内完成 100亿 en 10 + 3 secondes.

Mon ordinateur est i5-4210M 12G Chrome 58

JavaScript ne peut pas atteindre cette performance : JavaScript 做不到这样的性能： 100亿 个数字 13 nombres en 13 secondes....

Plusieurs G données...

Selon l'idée ci-dessus, même C/C++ on estime qu'il sera difficile d'exécuter 10 milliards en 13 secondes.

Concentrez-vous sur la résolution de problèmes.

Liens

Déterminez si un nombre est un nombre premier/un nombre premier - de l'algorithme de jugement ordinaire à l'idée d'un algorithme de jugement efficace

PHP中文网 · Answer

Tout d'abord, merci pour l'algorithme de recherche de nombres premiers à l'étage, je posterai mes résultats et mon code (seulement 10 millions, 100 millions de navigateurs ont directement explosé, et la récursion ne peut pas être utilisée pour trouver des nombres premiers (résultats de mon test), sinon je dois exploser, je ne peux qu'itérer).

Résultats dans le navigateur :

Le résultat dans

node :

var arr = [];

console.time("1000万");
for( var i = 1; i <= 10000000; i++ ){
    arr.push(i);
}

for( var j = 0, len = arr.length;j < len; j+=2 ){
    arr[j]++;
    arr[j+1]--;
}

function isPrime(num,sqrt){
     if(num == 1)
     return false;
     if(num == 2 || num == 3 )  
     return true;  
     if(num % 6 != 1 && num % 6 != 5)  
     return false;  
     var tmp = sqrt(num);  
     for(var i= 5;i<=tmp; i+=6 )  
        if(num % i == 0 || num % ( i + 2) == 0 )  
        return false ;  

     return true;  
};

function getPrime(sourceArray,array,isPrime,sqrt){

    sourceArray.map(function(num,idx){
        if(isPrime(num,sqrt)){
            array.push(num);
        }
    });

    return array;
};

var result = getPrime(arr,[],isPrime,Math.sqrt);

console.timeEnd("1000万");