javascript - programmation, problèmes d'algorithme

Question

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 les compléter (seulement dans les 3 secondes), même les nombres précèdent 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 : Sur le code de 1, il faut que le mot clé for while ne peut pas être utilisé, à partir de 100 Récupérer tous les nombres premiers sur 100 millions (le temps ne peut pas dépasser 3 secondes)
Comment faire ?

Answer 1

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 2

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.

Answer 3

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.

---

Suivant

1. Les nombres pairs en premier, les nombres impairs en dernier

Après observation, j'ai trouvé que 奇数 + 1、 偶数 - 1 allait bien

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

var res001 = test.map((e, idx) => {
    if (isEven(e)){
        return e - 1; 
    } else {
        return e + 1; 
    }
}); 

Répondez à la première question

Capture d'écran 1

Suivant

La question suivante est d'obtenir des nombres premiers basés sur ce qui précède, c'est-à-dire d'obtenir tous les nombres premiers de zs

J'ai recherché le problème des nombres premiers, et quelqu'un d'autre a dit 质数分布在 6 的倍数的左边或者右边 Ensuite, il me suffit de parcourir les côtés gauche et droit de chaque multiple de 6 et de déterminer s'il s'agit de nombres premiers.

Lien : Déterminer 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

// 剔除第一个负数 
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

Answer 4

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万");