Tìm kiếm trang web

bất đồng bộ - Javascript: Làm thế nào để điều khiển luồng với việc duyệt cây đệ quy bất đồng bộ?

Tôi cần đệ quy trên một cây để thực hiện các thao tác trên các nút cụ thể bằng các thao tác bất đồng bộ. Làm thế nào tôi có thể điều khiển luồng để có quyền truy cập vào các nút khi nó hoàn thành?

Đây là một tình huống ví dụ:

data = {
  name: "deven",
  children: [
    { name: "andrew" },
    { name: "donovan" },
    { name: "james",
      children: [
        { name: "donatello" },
        { name: "dan" }
      ]
    },
    { name: "jimmy",
      children: [
        { name: "mike" },
        { name: "dank" }
      ]
    }
  ]
};

Tôi có một hàm mục tiêu là duyệt qua cây và viết hoa tất cả các tên bắt đầu bằng 'd'. Sau đó, tôi muốn truyền cây vào một hàm khác để thực hiện thêm một số công việc (có thể xóa tất cả các nút có tên bắt đầu bằng 'a'), nhưng chỉ sau khi quá trình xử lý ban đầu đã được thực hiện:

function capitalize_d(node) {
    if(node.name === "d") {
        node.name = node.name.toUpperCase();
    }

    if(node.children != null) {
        for(var i = 0; i < node.children.length; i++) {
            capitalize_d(node.children[i]);
        }
    }
}

function remove_a(node) {
}

capitalize_d(data);

// Should only get called after all the d's have been capitalized.
remove_a(data);

Mã trên hoạt động tốt, vì capitalize_d là đồng bộ. Nếu capitalize_d gọi đệ quy bất đồng bộ, làm thế nào chúng ta có thể đảm bảo remove_a được gọi sau khi nó hoàn tất? Lưu ý lời gọi setTimeout trong capitalize_d.

function capitalize_d(node) {
    setTimeout(function() {

        if(node.name === "d") {
            node.name = node.name.toUpperCase();
        }

        if(node.children != null) {
            for(var i = 0; i < node.children.length; i++) {
                capitalize_d(node.children[i]);
            }
        }

    }, 1);
}

function remove_a(node) {
}

capitalize_d(data);

// Should only get called after all the d's have been capitalized.
remove_a(data);

Vấn đề là chúng tôi có các xử lý cho các nhánh khác nhau của cây đều được kích hoạt cùng một lúc, và không thể biết khi nào thì việc xử lý cây cuối cùng đã hoàn tất.

Làm thế nào tôi có thể giải quyết việc này?

Câu trả lời #1

Hãy để tôi tóm tắt những gì tôi hiểu về yêu cầu của bạn:

  • bạn có một cây dữ liệu nơi mỗi nút riêng lẻ có thể được thay đổi không đồng bộ bởi một tập hợp các thao tác (capitalize_d và remove_a trong ví dụ của bạn),
  • bạn muốn đảm bảo rằng từng nút riêng lẻ đã trải qua một thao tác nhất định trước khi cho phép nút tiếp theo.

Tôi đã dành 10 năm hoặc hơn để thiết kế phần mềm nhúng thời gian thực, và tin tôi đi, các yêu cầu trong lĩnh vực này khắc nghiệt và đáng sợ hơn bất cứ điều gì mà hầu hết các lập trình viên mạng sẽ trải qua trong suốt cuộc đời họ. Điều này khiến tôi phải cảnh báo bạn rằng dường như bạn đang đi theo hướng hoàn toàn sai lầm ở đây.

Theo như tôi có thể tưởng tượng, vấn đề của bạn là tổ chức một tập hợp các dữ liệu riêng lẻ thành một cấu trúc có ý nghĩa nào đó. Một số quá trình thu thập các mẩu thông tin ngẫu nhiên (những gì bạn gọi là 'nút' trong ví dụ của bạn), và vào một lúc nào đó bạn muốn đưa tất cả những nút đó vào một cấu trúc dữ liệu nhất quán, thống nhất (một cây phân cấp trong ví dụ của bạn).

Nói cách khác, bạn có ba nhiệm vụ cần thực hiện:

  • một quá trình thu thập dữ liệu sẽ thu thập các nút một cách bất đồng bộ
  • một quy trình sản xuất dữ liệu sẽ trình bày một cây dữ liệu nhất quán, tinh chế
  • một quy trình điều khiển sẽ đồng bộ hóa việc thu thập dữ liệu và sản xuất (có thể trực tiếp với giao diện người dùng nếu hai quy trình trên đủ thông minh, nhưng đừng quá trông đợi vào điều đó).

Lời khuyên của tôi: đừng cố gắng thực hiện việc tiếp nhận và sản xuất cùng một lúc.

Chỉ để cho bạn có ý tưởng về cơn ác mộng mà bạn sắp phải đối mặt:

  • tùy thuộc vào cách các thao tác được kích hoạt, có khả năng cây sẽ không bao giờ được xử lý hoàn toàn bởi một thao tác nhất định. Giả sử phần mềm điều khiển quên gọi capitalize_d trên một vài nút, remove_a sẽ đơn giản là không bao giờ nhận được tín hiệu cho phép

  • ngược lại, nếu bạn bắn vào cây một cách ngẫu nhiên, rất có khả năng một số nút sẽ bị xử lý nhiều lần, trừ khi bạn theo dõi phạm vi thao tác để ngăn việc áp dụng cùng một phép biến đổi hai lần cho một nút nhất định

  • nếu bạn muốn xử lý remove_a bắt đầu, bạn có thể phải ngăn phần mềm điều khiển gửi thêm bất kỳ yêu cầu capitalize_d nào, nếu không đèn có thể sẽ bị kẹt ở màu đỏ mãi mãi. Bạn sẽ kết thúc việc điều khiển luồng các yêu cầu của mình theo cách này hay cách khác (hoặc tệ hơn: bạn sẽ không làm gì cả, và hệ thống của bạn rất có khả năng bị treo nếu luồng vận hành đi lệch khỏi điểm thuận lợi mà bạn tình cờ đạt được).

  • nếu một thao tác làm thay đổi cấu trúc của cây (như remove_a rõ ràng làm), bạn phải ngăn chặn việc truy cập đồng thời. Ít nhất, bạn nên khóa cây con bắt đầu từ nút mà remove_a đang làm việc, nếu không bạn sẽ cho phép xử lý một cây con có khả năng bị thay đổi và/hoặc bị phá hủy bất đồng bộ.

Chà, điều đó có thể làm được. Tôi đã thấy những chàng trai trẻ tài giỏi kiếm được nhiều tiền nhờ thực hiện các biến thể của chủ đề này. Họ thường dành vài buổi tối mỗi tuần để ăn pizza trước màn hình máy tính, nhưng này, đó là cách bạn có thể phân biệt những hacker cứng rắn với đám đông những người ăn bánh quiche, đúng không?…

Tôi đoán việc bạn đăng câu hỏi này ở đây có nghĩa là bạn thực sự không muốn làm việc này. Bây giờ nếu sếp của bạn muốn, thì, để trích dẫn một robot nổi tiếng, tôi không thể nói dối bạn về cơ hội của bạn, nhưng... bạn có sự thông cảm của tôi.

Nào, nghiêm túc nào mọi người.. Đây là cách tôi sẽ giải quyết vấn đề.

1) chụp một bản sao dữ liệu của bạn tại một thời điểm nhất định

bạn có thể loại bỏ dữ liệu thô bằng cách sử dụng càng nhiều tiêu chí càng tốt (dữ liệu thu thập quá cũ, đầu vào sai, bất cứ điều gì cho phép bạn xây dựng cây nhỏ nhất có thể).

2) xây dựng cây với snapshot, sau đó áp dụng bất kỳ các thao tác capitalize_d, remove_a và camelize_z theo trình tự trên snapshot được cung cấp này.

Song song đó, quá trình thu thập dữ liệu sẽ tiếp tục thu thập các nút mới hoặc cập nhật các nút hiện có, sẵn sàng chụp ảnh nhanh tiếp theo.

Bên cạnh đó, bạn có thể chuyển một số xử lý của mình lên trước. Rõ ràng là capitalize_d không tận dụng được cấu trúc cây, vì vậy bạn có thể áp dụng capitalize_d cho từng nút trong ảnh chụp nhanh trước khi cây được xây dựng. Bạn thậm chí có thể áp dụng một số biến đổi sớm hơn, tức là trên từng mẫu được thu thập. Điều này có thể giúp bạn tiết kiệm rất nhiều thời gian xử lý và làm đơn giản mã nguồn.

Kết thúc bằng một chút lý thuyết sáo rỗng,

  • Cách tiếp cận của bạn là coi cây dữ liệu như một đối tượng chung nên hỗ trợ truy cập đồng thời từ các quy trình thu thập dữ liệu và sản xuất dữ liệu.
  • Phương pháp của tôi là làm cho quy trình thu thập dữ liệu phục vụ (một cách không đồng bộ) các bộ dữ liệu nhất quán cho một quy trình sản xuất dữ liệu, sau đó có thể xử lý theo thứ tự các bộ dữ liệu nói trên.

quy trình sản xuất dữ liệu có thể được kích hoạt theo yêu cầu (ví dụ khi người dùng cuối nhấn nút "show me something"), trong trường hợp này tính phản ứng sẽ khá kém: người dùng sẽ phải chờ xem một đồng hồ cát hoặc bất kỳ vòng quay hấp dẫn nào của Web2.0 trong thời gian cần để xây dựng và xử lý cây (giả sử khoảng 7-8 giây).

hoặc bạn có thể kích hoạt quá trình sản xuất dữ liệu định kỳ (cung cấp cho nó một bản chụp mới mỗi 10 giây, một khoảng thời gian an toàn hơn thời gian xử lý trung bình của một bộ dữ liệu). Nút "hiển thị cho tôi một cái gì đó" sau đó chỉ trình bày bộ dữ liệu đã hoàn thành gần nhất. Một câu trả lời ngay lập tức, nhưng với dữ liệu có thể cũ hơn 10 giây so với các mẫu cuối cùng nhận được.

Tôi hiếm khi thấy trường hợp nào mà điều này không được coi là chấp nhận được, đặc biệt là khi bạn tạo ra một loạt dữ liệu phức tạp mà một người điều hành cần vài chục giây để tiếp nhận.

Về lý thuyết, phương pháp của tôi sẽ mất một phần phản ứng, vì dữ liệu được xử lý sẽ hơi lỗi thời, nhưng phương pháp truy cập đồng thời có lẽ sẽ dẫn đến phần mềm chậm hơn nữa (và chắc chắn lớn hơn và lỗi hơn 5-10 lần).

Câu trả lời #2

Tôi biết bài đăng này đã cũ, nhưng nó xuất hiện trong kết quả tìm kiếm, và câu trả lời duy nhất không cung cấp một ví dụ hoạt động, vì vậy đây là phiên bản đã chỉnh sửa của một thứ gì đó tôi vừa làm gần đây...

function processTree(rootNode, onComplete) {

    // Count of outstanding requests.
    // Upon a return of any request,
    // if this count is zero, we know we're done.
    var outstandingRequests = 0;

    // A list of processed nodes,
    // which is used to handle artifacts
    // of non-tree graphs (cycles, etc).
    // Technically, since we're processing a "tree",
    // this logic isn't needed, and could be
    // completely removed.
    //
    // ... but this also gives us something to inspect
    // in the sample test code. :)
    var processedNodes = [];

    function markRequestStart() {
        outstandingRequests++;
    }

    function markRequestComplete() {
        outstandingRequests--;
        // We're done, let's execute the overall callback
        if (outstandingRequests < 1) { onComplete(processedNodes); }
    }

    function processNode(node) {
        // Kickoff request for this node
        markRequestStart();
        // (We use a regular HTTP GET request as a
        // stand-in for any asynchronous action)
        jQuery.get("/?uid="+node.uid, function(data) {
            processedNodes[node.uid] = data;
        }).fail(function() {
            console.log("Request failed!");
        }).always(function() {
            // When the request returns:
            // 1) Mark it as complete in the ref count
            // 2) Execute the overall callback if the ref count hits zero
            markRequestComplete();
        });

        // Recursively process all child nodes (kicking off requests for each)
        node.children.forEach(function (childNode) {
            // Only process nodes not already processed
            // (only happens for non-tree graphs,
            // which could include cycles or multi-parent nodes)
            if (processedNodes.indexOf(childNode.uid) < 0) {
                processNode(childNode);
            }
        });

    }

    processNode(rootNode);
}

Và đây là ví dụ sử dụng với QUnit:

QUnit.test( "async-example", function( assert ) {
    var done = assert.async();

    var root = {
        uid: "Root",
        children: [{
            uid: "Node A",
            children: [{
                uid: "Node A.A",
                children: []
            }]
        },{
            uid: "Node B",
            children: []
        }]
    };

    processTree(root, function(processedNodes) {
        assert.equal(Object.keys(processedNodes).length, 4);
        assert.ok(processedNodes['Root']);
        assert.ok(processedNodes['Node A']);
        assert.ok(processedNodes['Node A.A']);
        assert.ok(processedNodes['Node B']);
        done();
    });
});