我有一个可能有数千个物体的模型.我想知道什么是最有效的存储方式和一旦我拥有它的id后检索单个对象.id是长号.
所以这些是我想到的两个选项.在选项1中,它是一个带有递增索引的简单数组.在选项2中,它是一个关联数组,也许是一个对象,如果它有所不同.我的问题是哪一个更有效,当我主要需要检索单个对象,但有时也循环遍历它们并进行排序.
选项一,非关联数组:
var a = [{id: 29938, name: 'name1'},
{id: 32994, name: 'name1'}];
function getObject(id) {
for (var i=0; i < a.length; i++) {
if (a[i].id == id)
return a[i];
}
}
选项二与关联数组:
var a = []; // maybe {} makes a difference?
a[29938] = {id: 29938, name: 'name1'};
a[32994] = {id: 32994, name: 'name1'};
function getObject(id) {
return a[id];
}
更新:
好的,我知道在第二个选项中使用数组是不可能的.因此第二个选项的声明行应该是:var a = {};并且唯一的问题是:在检索具有给定id的对象时表现更好:数组或id为关键字的对象.
而且,如果我必须多次对列表进行排序,答案会改变吗？
通过添加和删除项目,可以非常轻松地修改JavaScript中的数组.它有点掩盖了大多数语言数组是固定大小的事实,并且需要复杂的操作来调整大小.似乎JavaScript可以很容易地编写性能不佳的数组代码.这导致了一个问题:
在数组性能方面,我可以从JavaScript实现中获得什么样的性能(就大O时间复杂度而言)？
我假设所有合理的JavaScript实现至少具有以下大O.
JavaScript允许您使用new Array(length)语法将数组预填充到特定大小.(额外的问题:以这种方式创建一个数组O(1)或O(n))这更像是一个传统的数组,如果用作预先调整大小的数组,可以允许O(1)追加.如果添加了循环缓冲逻辑,则可以实现O(1)前置.如果使用动态扩展数组,则O(log n)将是这两者的平均情况.
对于某些事情,我可以期待比我的假设更好的表现吗？我不希望在任何规范中概述任何内容,但实际上可能是所有主要实现都在后台使用优化的数组.是否有动态扩展阵列或其他一些性能提升算法？
PS
我想知道这个的原因是因为我正在研究一些排序算法,其中大多数似乎假设在描述它们的整体大O时附加和删除是O(1)操作.
我想打印前10000个素数.任何人都可以给我最有效的代码吗？澄清:
我一直在尝试用JavaScript 编写Sieve of Eratosthenes算法.基本上我只是遵循以下步骤:
这就是我想出的:
function eratosthenes(n){
var array = [];
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,...
var maxPrimeFactor = 0;
var upperLimit = Math.sqrt(n);
var output = [];
// Eratosthenes algorithm to find all primes under n
// Make an array from 2 to (n - 1)
//used as a base array to delete composite number from
for(var i = 2; i < n; i++){
array.push(i); …素数的生成很简单但是找到它并以递归方式生成(素数)的最快方法是什么？
这是我的解决方案.但是,这不是最好的方法.我认为它是O(N*sqrt(N)).如果我错了,请纠正我.
public static boolean isPrime(int n) {
if (n < 2) {
return false;
} else if (n % 2 == 0 & n != 2) {
return false;
} else {
return isPrime(n, (int) Math.sqrt(n));
}
}
private static boolean isPrime(int n, int i) {
if (i < 2) {
return true;
} else if (n % i == 0) {
return false;
} else {
return isPrime(n, --i);
}
}
public static void generatePrimes(int n){
if(n < …我试图在一行Python中创建素数生成器,这只是一个有趣的练习.
以下代码按预期工作,但速度太慢:
primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
for i in primes(10):
print i,
所以我试图通过检查j和k的平方根来做到这一点:
primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,int(round(math.sqrt(i)+1))) for k in xrange(1,int(round(math.sqrt(i)+1)))])
for i in primes(10):
print i,
但它输出: 2 3 5 6 7 8
所以我的指数j和k肯定有问题,但我没有线索.
var sum = 0
for (i = 0; i < 250; i++) {
function checkIfPrime() {
for (factor = 2; factor < i; factor++) {
if (i % factor = 0) {
sum = sum;
}
else {
sum += factor;
}
}
}
}
document.write(sum);
我试图检查250以下的所有素数的总和.我收到一个错误,说我在if (i % factor = 0)我原来的语句中创建的语句中无效,但有没有办法在if中引用它声明？
标准埃拉托斯特尼筛法多次剔除大多数复合材料；事实上，唯一不会被标记多次的就是那些恰好是两个素数的乘积。当然，随着筛子变大，透支也会增加。
对于奇数筛（即没有偶数），透支达到 100%（n = 3,509,227），其中有 1,503,868 个复合值和 1,503,868 个已划掉的数字的划掉。对于 n = 2^32，透支上升至 134.25%（透支 2,610,022,328 与弹出计数 1,944,203,427 = (2^32 / 2) - 203,280,221）。
当且仅当循环限制是智能计算的时， Sundaram 筛法（在maths.org上有另一种解释）可能会更聪明一些。然而，我所看到的消息来源似乎将其掩盖为“优化”，而且似乎未优化的 Sundaram 每次都会被仅赔率的埃拉托色尼击败。
有趣的是，两者都创建了完全相同的最终位图，即位图 k 对应于数字 (2 * k + 1)。因此，两种算法最终必须设置完全相同的位，只是它们的处理方式不同。
有人拥有竞技性、调校 Sundaram 的实践经验吗？它能打败古希腊语吗？
我精简了小因子筛的代码（2^32，仅赔率的希腊语），并将段大小调整为 256 KB，这对于具有 256 KB L2 的旧 Nehalem 和较新的 CPU 来说都是最佳的（甚至尽管后者对更大的细分市场更加宽容）。但现在我已经碰壁了，该死的筛子仍然需要 8.5 秒来初始化。从硬盘加载筛子并不是一个非常有吸引力的选择，并且多线程很难以可移植的方式完成（因为像 boost 这样的库往往会增加可移植性）...
Sundaram 能否将启动时间缩短几秒钟？
PS：透支本身不是问题，会被二级缓存吸收。关键是，标准的埃拉托斯特尼似乎做了比必要的工作多一倍的工作，这表明可能有可能更快地完成更少的工作。
我正在做一个练习，对从 2 到参数的所有素数求和。我已经在代码中工作了这么远，但我被卡住了。我相信通过使用 splice 函数，我实际上跳过了一个元素，因为索引发生了变化。
function sumPrimes(num) {
var primearray = [];
var sum = 0;
for(var i =2; i <= num; i++){
primearray.push(i);
}
for(var j = 0; j < primearray.length; j++) {
console.log(primearray[j]);
if ((primearray[j]%2===0) && (primearray[j] >2)) {
primearray.splice(j,1);
} else if ((primearray[j]%3===0) && (primearray[j] > 3)) {
primearray.splice(j,1);
console.log(primearray);
} else if ((primearray[j]%5===0) && (primearray[j] > 5)) {
primearray.splice(j,1);
} else if ((primearray[j]%7===0) && (primearray[j] > 7)) {
primearray.splice(j,1);
}
}
sum = primearray.reduce();
return sum; …我最近阅读了有关大量数字的更快的Eratosthenes分段筛网实施方案的信息。
以下是相同的实现：
function sieve(low, high) {
var primeArray = [], ll = Math.sqrt(low), output = [];
for (var i = 0; i < high; i++) {
primeArray[i] = true;
}
for (var i = 2; i <= ll; i++) {
if (primeArray[i]) {
for (var j = i * i; j < high; j += i) {
primeArray[j] = false;
}
}
}
for (var i = 2; i < ll; i++) {
if(primeArray[i])
{
var segmentStart = Math.floor(low/i) * …附件是用于查找2个数字之间的所有素数的代码.t作为测试用例的数量n,m分别是上限和下限.我运行这个程序,它一直给我sigsegv错误.
#include <iostream>
using namespace std;
int Prime1(int n,int m)
{
int i,j;
//cout<<"Enter :"<<endl;
//cin>>n;
int x[n];
for(i=0;i<=n;i++)
{
x[i]=1;
}
for(i=4;i<=n;i+=2)
{
x[i]=0;
}
for(i=3;i<=n;i+=2)
{
if(x[i])
{
for(j=2*i;j<=n;j+=i)
{
x[j]=0;
}
}
}
if(m==1)
{
m=m+1;}
for(i=m;i<=n;i++)
{
if(x[i])
{
cout<<i<<endl;;
}
}
}
int main()
{
int x,y,t;
cin>>t;
while(t!=0)
{
cin>>x>>y;
cout<<endl;
if(x>y)
{
Prime1(x,y);
}
else
{
Prime1(y,x);
}
t--;
}
system("pause");
}
试图找出一个函数来检查一个数字是否为素数并且我遇到了麻烦.我确定有一种更简单的方法可以做到这一点,但为什么这个函数不会返回false,对于数字9？它为偶数返回false,但对于任何其他类型的复合数,它返回undefined,但由于它打印NOT PRIME,它也应该返回false.
function isPrime(n, i) {
document.writeln(i);
var nextNum = i + 1;
var number = n;
if (i < n) {
if ((n % i) === 0) {
document.writeln("NOT PRIME");
return false;
} else {
document.writeln(nextNum);
isPrime(number, nextNum);
}
} else if (i === n) {
document.writeln("Recursion ends");
return true;
} else {
document.writeln("Confused" + typeof i + typeof n);
}
}