为什么这段代码这么慢？

jsc.tools.road.correctType = function() {
    for(row = jsc.data.selection.startX - 1; row <= jsc.data.selection.endX + 1; row++) {
        for(col = jsc.data.selection.startY - 1; col <= jsc.data.selection.endY + 1; col++) {
            if(jsc.data.cells[row-1][col].type != "road" && jsc.data.cells[row+1][col].type != "road" && jsc.data.cells[row][col].type == "road") {
                jsc.ui.addClassToCell("horz", row, col);
            }
            else {
                jsc.ui.removeClassFromCell("horz", row, col);
            }
            if(jsc.data.cells[row][col-1].type != "road" && jsc.data.cells[row][col+1].type != "road" && jsc.data.cells[row][col].type == "road") {
                jsc.ui.addClassToCell("vert", row, col);
            }
            else {
                jsc.ui.removeClassFromCell("vert", row, col);
            }
        }
    }
};

// Elsewhere
jsc.ui.addClassToCell = function(class, x, y) {
    $("#" + x + "-" + y).addClass(class);
};
jsc.ui.removeClassFromCell = function(class, x, y) {
    $("#" + x + "-" + y).removeClass(class);
};

The code above runs very slowly. I can't figure out why. It's using jQuery 1.3.2. Any way to optimize it a bit?

上面的代码运行得非常慢。我无法弄清楚为什么。它使用的是jQuery 1.3.2。有什么方法可以优化它吗?

EDIT: The code is part of a javascript game I am making as a personal project. It's basically a Simcity clone. This piece of code checks the neighbouring cells for each part of the road, and changes the class (and in turn the background image) to the correct one to make the road images line up right, e.g. horizontal, vertical and junction(no class) road images.

编辑:代码是我作为个人项目制作的JavaScript游戏的一部分。它基本上是一个Simcity克隆。这段代码检查道路的每个部分的相邻单元,并将类(以及背景图像)改变为正确的单元以使道路图像正确排列,例如,水平,垂直和交叉(无类)道路图像。

EDIT 2: A few more details to provide some context.

编辑2:提供一些上下文的更多细节。

The jsc.data.cells is an 200 x 200 array. Each array element is an object with properties like so (default shown): {type: null, developed: false, powered: false, watered: false, hasTransport: false, wealth: 0, quality: 0} .

jsc.data.cells是一个200 x 200的数组。每个数组元素都是一个具有如此属性的对象(默认显示):{type:null,develop:false,powered:false,watered:false,hasTransport:false,wealth:0,quality:0}。

It's counterpart is in the UI, which is basically a giant table. (200 x 200 again). Each cell has a number of CSS classes added to it throughout the program to change the background image (e.g. .road to change it to road, .com.developed to make it a developed commercial zone). The table cells each have an id of the form #x-y which is what jsc.ui.addClassToCell, and jsc.ui.removeClassFromCell edit.

它与UI相对应,它基本上是一个巨大的表。 (再次200 x 200)。每个单元格在整个程序中都添加了许多CSS类,以更改背景图像(例如,将其更改为道路,.com.developed以使其成为开发的商业区域)。表格单元格的每个都具有#x-y形式的id,即jsc.ui.addClassToCell和jsc.ui.removeClassFromCell编辑的形式。

EDIT 3: Fixed the IDs starting with numbers. Trying out some of the optimizations now.

编辑3:修复了以数字开头的ID。现在尝试一些优化。

5 个解决方案

#1

Normally you can significantly optimize loops like these;

通常,您可以显着优化这些循环;

for( var x = 0; x < someMethod(); x++ ) {
  //... do stuff
}

By exchanging them out with something like this

用这样的东西换掉它们

var x = someMethod();
while( x-- ) {
  //...do stuff
}

Though it becomes slightly different semantically, it normally works quite well as long as you're not dependent upon order in your looping (order is opposite)

虽然它在语义上略有不同,但只要你不依赖循环中的顺序(顺序相反),它通常就能很好地工作。

Even when you cannot change the order, you will also significantly improve your code by merely moving the someMethod call OUT of your actual loop, since in many JS implementations it will be called once for every iteration...

即使你不能改变顺序,你也可以通过移动实际循环的someMethod调用OUT来显着改进代码,因为在许多JS实现中,每次迭代都会调用一次...

#2

A short estimate using O() notation:

使用O()表示法的简短估计:

for(row) ... O(N)
for(col) ... O(N)
$().addClass/removeClass ... O(N^2)

the $() is even called twice within the nested for.

$()甚至在嵌套for中被调用两次。

so you end up with O(N^4)

所以你最终得到O(N ^ 4)

You can optimize this by caching the calculated classes in the as property of jsc.data.cells[row][col], e.g.

您可以通过在jsc.data.cells [row] [col]的as属性中缓存计算出的类来优化它,例如:

jsc.data.cells[row][col].horz = 1; // don't set class "horz" if not present
jsc.data.cells[row][col].vert = 1;

and use the cached data when you create the cells inside the HTML table, rather than calling $() for each cell.

并在HTML表格中创建单元格时使用缓存数据,而不是为每个单元格调用$()。

#3

Depending on the size of your selection, you might be doing a whole lot of condition checks and DOM edits.

根据您选择的大小,您可能正在进行大量的条件检查和DOM编辑。

By commenting out the content of addClassToCell and removeClassFromCell and comparing run times you can find out whether the condition checking or the dom editing takes the most time and thus which one is the best candidate for optimising.

通过注释掉addClassToCell和removeClassFromCell的内容并比较运行时间,您可以了解条件检查或dom编辑是否花费最多时间,从而确定哪一个是优化的最佳候选者。

#4

I can only give some tips, but don't know if they help much. Have no possibility to test your code.

我只能给出一些提示,但不知道它们是否有用。无法测试您的代码。

1-st: declare variables in local function scope. I mean the row and col variables, which you declared as global (missing var statement). Access to global variables takes longer (AFAIK) than to local scope vars.

1-st:在本地函数范围内声明变量。我的意思是行和col变量,您声明为全局变量(缺少var语句)。对全局变量的访问需要更长时间(AFAIK),而不是本地范围变量。

var row = jsc.data.selection.startX-1;

var col = jsc.data.selection.startY-1;

2-nd: cache references to common objects. Here, you can store reference for jsc.data and/ord jsc.data.selection and jsc.data.cells. IIRC, the access to an object property is linear.

2-nd:缓存对公共对象的引用。在这里,您可以存储jsc.data和/或jsc.data.selection和jsc.data.cells的引用。 IIRC,对象属性的访问是线性的。

jsc.tools.road.correctType = function() {
   var data = jsc.data, selection = data.selection, cells = jsc.data.cells, ui.jsc.ui;

   for(var row = selection.startX - 1, endX = selection.endX + 1, endY = selection.endY + 1; row <= endX; ++row) {
      for(var col = selection.startY - 1; col <= endY; ++col) {
         if(cells[row-1][col].type != "road" && cells[row+1][col].type != "road" && cells[row][col].type == "road") {
            ui.addClassToCell("horz", row, col);
         } else {
            ui.removeClassFromCell("horz", row, col);
         }
         if(cells[row][col-1].type != "road" && cells[row][col+1].type != "road" && cells[row][col].type == "road") {
            ui.addClassToCell("vert", row, col);
         } else {
            ui.removeClassFromCell("vert", row, col);
         }
      }
   }
};

I also moved the declaration of endY variable to the outer loop, so it won't be computed with every access to inner loop.

我还将endY变量的声明移动到外部循环,因此不会在每次访问内部循环时计算它。

-- edit

hope you know, that ID attribute values cannot start with a number, like you have, eg. #2-3

希望你知道,ID属性值不能以数字开头,就像你拥有的那样,例如。 #2-3

#5

Use a memoizer or a local cache to store the jQuery objects you have already created. That will reduce the numer of calls of the $ function.

使用memoizer或本地缓存来存储您已创建的jQuery对象。这将减少$函数调用的数量。

var cache = {}, selector;
for (/* … */) {
    selector = "#" + x + "-" + y;
    if (!cache[selector]) {
        cache[selector] = $(selector);
    }
    // cache[selector] refers to the same object as $("#" + x + "-" + y)
}

#1