Javascript: Làm cách nào để kiểm soát luồng với quá trình truyền tải cây đệ quy không đồng bộ?

Question

Tôi cần phải recurse trên một cây để thực hiện các hoạt động trên các nút cụ thể bằng cách sử dụng các hoạt động không đồng bộ. Làm thế nào tôi có thể kiểm soát lưu lượng để tôi có quyền truy cập vào các nút khi nó được thực hiện?

Dưới đâ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 chức năng người là mục tiêu của nó là để lặp qua cây và tận dụng tất cả các tên bắt đầu bằng 'd'. Sau đó, tôi muốn vượt qua cây vào chức năng khác để làm một số công việc nhiều hơn (có thể xóa tất cả các nút mà có một cái tên bắt đầu với 'a'), nhưng chỉ sau khi 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); 

Đoạn mã trên hoạt động tốt, bởi vì capitalize_d đang chặn. Nếu capitalize_d đệ quy không đồng bộ, làm cách nào chúng tôi có thể đảm bảo remove_a được gọi sau khi hoàn thành? Lưu ý cuộc 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 đã xử lý cho các nhánh khác nhau của cây đều bị bắn cùng lúc và không thể biết khi nào nó xử lý xong cây.

Tôi làm cách nào để giải quyết vấn đề này?

Answer 1

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

• bạn có một cây dữ liệu mà mỗi nút duy nhất có thể được thay đổi không đồng bộ bởi một tập hợp các hoạt động (capitalize_d và remove_a trong ví dụ của bạn),
• bạn muốn đảm bảo rằng mọi nút đơn đã phải chịu một hoạt động 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 có ý nghĩa hơn và sợ hãi hơn bất cứ thứ gì mà hầu hết các lập trình viên mạng sẽ trải nghiệm trong suốt cuộc đời của họ. Điều này làm cho tôi cảnh báo bạn rằng bạn dường như đang đứng đầu một cách nghiêm túc sai lầm ở đây.

Như tôi có thể hình dung, vấn đề của bạn là tổ chức một tập hợp dữ liệu riêng lẻ trong một số loại cấu trúc có ý nghĩa. Một số quy trình thu thập các bit thông tin ngẫu nhiên (cái mà bạn gọi là 'nút' trong ví dụ của bạn), và tại một thời điểm nào đó bạn muốn đặt tất cả các nút đó vào một cấu trúc dữ liệu nguyên khối, nhất quán (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ụ trong tầm tay:

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

Lời khuyên của tôi: không cố gắng làm mua lại và sản xuất cùng lúc.

Chỉ cần để cung cấp cho bạn một ý tưởng về những cơn ác mộng bạn đang hướng đến:

• tùy thuộc vào cách hoạt động được kích hoạt, có một khả năng rằng cây sẽ không bao giờ được hoàn toàn xử lý bởi một hoạt động trao . 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ẽ không bao giờ nhận được ánh sáng màu xanh lá cây

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

• nếu bạn muốn remove_a chế biến bao giờ bắt đầu, bạn có thể có để ngăn chặn các phần mềm điều khiển từ gửi nữa capitalize_d yêu cầu, hoặc nếu không ánh sáng có thể vẫn bị kẹt lại màu đỏ mãi mãi. Bạn sẽ kết thúc kiểm soát luồng theo yêu cầu của bạn theo cách này hay cách khác (hoặc tệ hơn: bạn sẽ không làm bất kỳ điều gì, và hệ thống của bạn có thể bị đóng băng đến chết nên luồng hoạt động đi xa khỏi điểm ngọt mà bạn tình cờ gặp phải).

• nếu hoạt động thay đổi cấu trúc của cây (như remove_a rõ ràng là không), bạn phải ngăn truy cập đồng thời. Ít nhất, bạn nên khóa cây con bắt đầu từ nút remove_a đang hoạt động, 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ị hủy không đồng bộ.

Cũng có thể thực hiện được. Tôi đã nhìn thấy người đàn ông youg tốt kiếm tiền lớn làm biến thể về chủ đề này. Họ thường dành một vài buổi tối mỗi tuần ăn bánh pizza trước máy tính của họ quá, nhưng hey, đó là cách bạn có thể nói với ... Read More câu hỏi ở đây có nghĩa là bạn không thực sự muốn làm điều này. Bây giờ nếu ông chủ của bạn làm, tốt, để trích dẫn một android 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ự đồng cảm của tôi.

Bây giờ là những người nghiêm túc .. Đây là cách tôi giải quyết vấn đề.

1) có một bản chụp của dữ liệu của bạn tại một thời điểm cho trước

bạn có thể loại bỏ dữ liệu thô sử dụng như nhiều tiêu chí như bạn có thể (cuối cùng thu thập dữ liệu quá cũ, đầu vào không chính xác, 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 ảnh chụp nhanh và sau đó áp dụng bất kỳ hoạt động capitalize_d, remove_a và camelize_z nào tuần tự trên ảnh chụp đã cho 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 tiếp theo.

Bên cạnh đó, bạn có thể chuyển một số tiến trình xử lý của mình về phía trước. Rõ ràng là capitalize_d không tận dụng lợi thế của cấu trúc cây, vì vậy bạn có thể áp dụng capitalize_d cho mỗi nút trong ảnh chụp nhanh trước khi cây thậm chí được tạo. Bạn thậm chí có thể áp dụng một số biến đổi trước đó, tức là trên mỗi 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à mã phức tạp.

Để kết thúc với một chút lảm nhảm theroretical,

• cách tiếp cận của bạn là để xem xét cây dữ liệu một đối tượng chia sẻ rằng nên hỗ trợ acces đồng thời từ các quá trình thu thập dữ liệu và sản xuất dữ liệu,
• cách tiếp cận của tôi là để làm cho quá trình thu thập dữ liệu phân phối (không đồng bộ) các tập hợp 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ý tuần tự bộ dữ liệu đã nói.

quy trình sản xuất dữ liệu có thể được kích hoạt theo yêu cầu (khi người dùng cuối nhấp vào nút "hiển thị cho tôi cái gì đó"), trong trường hợp đó, phản ứng sẽ kém: người dùng sẽ bị kẹt xem đồng hồ cát hoặc bất cứ điều gì Web2.0 sexy quay bánh xe cho thời gian cần thiết để xây dựng và xử lý cây (cho phép nói 7-8 giây).

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

Tôi hiếm khi thấy các trường hợp không được coi là chấp nhận được, đặc biệt khi bạn tạo ra một loạt dữ liệu phức tạp mà người vận hành cần vài chục giây để tiêu hóa. Về lý thuyết, cách tiếp cận của tôi sẽ mất một số phản ứng, vì dữ liệu được xử lý sẽ hơi lỗi thời, nhưng cách tiếp cận đồng thời có thể dẫn đến phần mềm chậm hơn (và chắc chắn lớn hơn 5-10 lần và buggier).

Answer 2

Tôi biết bài này là cũ, nhưng nó đã đưa ra trong kết quả tìm kiếm, và phản ứng duy nhất không cung cấp một ví dụ làm việc, vì vậy đây là một phiên bản sửa đổi của một cái gì đó gần đây tôi đã làm ...

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ụ về cách sử dụng 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(); 
    }); 
});