Loại phân loại này là gì?

Question

Giả sử tôi có một danh sách các số nguyên, trong đó mỗi phần tử là một số từ 1 đến 20. (Đó không phải là những gì tôi đang cố sắp xếp.)

Bây giờ, tôi có một loạt các "hoạt động", trong đó mỗi hoạt động:

• Loại bỏ nhất định (biết) số điện thoại từ danh sách
• vàThêm nhất định khác số (được gọi) vào danh sách
• và là không có khả năng xử lý danh sách nếu nó có chứa một số số (biết) vào đầu hoạt động - gọi những Ngăn chặn

Edit: Có thể có không hoặc nhiều số trong mỗi Thêm , Xóa và Ngăn chặn cho mỗi thao tác và mỗi số có thể xuất hiện 0 hoặc nhiều lần trong mỗi nhóm đối với một số thao tác. Đối với bất kỳ hoạt động nào đó, Thêm và Loại bỏ là rời nhau, Ngăn chặn và Loại bỏ là rời nhau, nhưng Thêm và Ngăn chặn có thể chồng chéo.

Tôi muốn sắp xếp các mảng hoạt động để cho mỗi hoạt động:

• Nếu hoạt động có Ngăn chặn mục, nó được đặt sau một ca phẫu rằng Loại bỏ những con số. Nếu không ngay sau đó, không thể có hoạt động Thêm hoạt động thêm số đó vào giữa Xóa và ngăn chặn trước.
• Nếu hoạt động Xóa mục, tất cả các hoạt động Thêm bất kỳ mục nào trong số những mục này được đặt trước đó.

Trong trường hợp phụ thuộc vòng tròn, chuỗi hoạt động nên xóa càng nhiều số càng tốt và thông báo với tôi rằng nó không thể xóa tất cả các số.

Có tên/triển khai cho loại thuật toán này hoạt động tốt hơn thuật toán tôi có dưới đây không?

Đã thêm 8/23: Tiền thưởng bao gồm các yêu cầu sắp xếp xem xét cả OpCodes (bộ cấu trúc) và InstructionSemantics (bộ cờ bit từ một điều tra).

Đã thêm sau 8/23: Tôi đã thực hiện cải tiến hiệu suất 89: 1 bằng cách sắp xếp trước các mảng nguồn. Xem câu trả lời hiện tại của tôi để biết chi tiết.

namespace Pimp.Vmx.Compiler.Transforms 
{ 
    using System; 
    using System.Collections.Generic; 
    using System.Reflection.Emit; 

    internal interface ITransform 
    { 
     IEnumerable<OpCode> RemovedOpCodes { get; } 
     IEnumerable<OpCode> InsertedOpCodes { get; } 
     IEnumerable<OpCode> PreventOpCodes { get; } 

     InstructionSemantics RemovedSemantics { get; } 
     InstructionSemantics InsertedSemantics { get; } 
     InstructionSemantics PreventSemantics { get; } 
    } 

    [Flags] 
    internal enum InstructionSemantics 
    { 
     None, 
     ReadBarrier = 1 << 0, 
     WriteBarrier = 1 << 1, 
     BoundsCheck = 1 << 2, 
     NullCheck = 1 << 3, 
     DivideByZeroCheck = 1 << 4, 
     AlignmentCheck = 1 << 5, 
     ArrayElementTypeCheck = 1 << 6, 
    } 

    internal class ExampleUtilityClass 
    { 
     public static ITransform[] SortTransforms(ITransform[] transforms) 
     { 
      throw new MissingMethodException("Gotta do something about this..."); 
     } 
    } 
} 

---

Chỉnh sửa: Dưới dòng này là thông tin cơ bản về những gì tôi đang thực sự làm, trong trường hợp người đang tự hỏi tại sao tôi yêu cầu này. Nó không thay đổi vấn đề, chỉ hiển thị phạm vi.

Tôi có một hệ thống đọc trong danh sách các mục và gửi đến một "mô-đun" khác để xử lý. Mỗi mục là một lệnh trong biểu diễn trung gian của tôi trong trình biên dịch - về cơ bản là một số từ 1 đến ~ 300 cộng với một số kết hợp của khoảng 17 biến tố sẵn có (đếm cờ). Sự phức tạp của hệ thống xử lý (bộ mã máy) là tỷ lệ thuận với số lượng đầu vào duy nhất có thể (số + cờ), nơi tôi phải viết tay mọi bộ xử lý đơn lẻ. Trên hết, tôi phải viết ít nhất 3 hệ thống xử lý độc lập (X86, X64, ARM) - số lượng mã xử lý thực tế mà tôi có thể sử dụng cho nhiều hệ thống xử lý là tối thiểu.

Bằng cách chèn "hoạt động" giữa đọc và xử lý, tôi có thể đảm bảo rằng các mục nhất định không bao giờ xuất hiện để xử lý - tôi làm điều này bằng cách biểu thị số và/hoặc cờ theo các số khác. Tôi có thể mã hóa từng "hoạt động chuyển đổi" trong một hộp đen bằng cách mô tả các hiệu ứng của nó, giúp tôi tiết kiệm rất nhiều sự phức tạp cho mỗi hoạt động. Các phép toán phức tạp và duy nhất cho mỗi phép biến đổi, nhưng dễ dàng hơn nhiều so với hệ thống xử lý. Để hiển thị bao nhiêu thời gian này tiết kiệm, một trong các hoạt động của tôi hoàn toàn loại bỏ 6 lá cờ bằng cách viết các hiệu ứng mong muốn của chúng về mặt số 6 số (không có cờ).

Để giữ mọi thứ trong hộp đen, tôi muốn có thuật toán đặt hàng để thực hiện tất cả các hoạt động tôi viết, yêu cầu chúng có tác động lớn nhất và thông báo cho tôi về cách đơn giản hóa dữ liệu đạt được (các) hệ thống xử lý. Đương nhiên, tôi đang nhắm mục tiêu các mục phức tạp nhất trong phần trình bày trung gian và đơn giản hóa chúng thành số học con trỏ cơ bản nếu có thể, đó là cách dễ nhất để xử lý trong các bộ ghép. :)

Với tất cả những gì đã nói, tôi sẽ thêm ghi chú khác. Các hiệu ứng hoạt động được mô tả là "các hiệu ứng thuộc tính" trong danh sách các hướng dẫn. Nói chung các hoạt động hoạt động tốt, nhưng một số người trong số họ chỉ loại bỏ các con số rơi sau khi các số khác (như loại bỏ tất cả 6 mà không theo một 16). Những người khác loại bỏ tất cả các trường hợp của một số cụ thể có chứa các cờ nhất định. Tôi sẽ xử lý những điều này sau - SAU KHI tôi tìm ra vấn đề cơ bản về bảo đảm thêm/xóa/ngăn chặn được liệt kê ở trên.

Added 8/23:In this image, bạn có thể thấy một hướng dẫn call (màu xám) mà đã có InstructionSemantics.NullCheck được xử lý bởi các RemoveNullReferenceChecks biến để loại bỏ các ngữ nghĩa lá cờ để đổi lấy thêm một cuộc gọi (không có ngữ nghĩa gắn liền với bổ sung gọi một trong hai). Bây giờ người lắp ráp không cần phải hiểu/xử lý InstructionSemantics.NullCheck, bởi vì nó sẽ không bao giờ nhìn thấy chúng. Không chỉ trích mã ARM - it's a placeholder for now.

Answer 1

Tính năng này hoạt động ngay bây giờ. Nếu và chỉ khi một đơn hàng tồn tại để đáp ứng các điều kiện, nó sẽ tìm thấy nó. Tôi chưa thử tối ưu hóa nó. Nó hoạt động ngược lại bằng cách theo dõi các mục nào không được phép thêm vào bởi thao tác trước đó.

Chỉnh sửa: Tôi không thể đánh dấu câu trả lời này vì tôi đã thực hiện một hiệu suất rất lớn từ nó và tôi chỉ có 17 thao tác (ITransform s). Phải mất 15 giây để sắp xếp ngay bây giờ lol/thất bại.

Nhập 8/23: Kiểm tra phần mã tiếp theo để biết cách tôi cải thiện sắp xếp thành thứ gì đó thực sự khả thi một lần nữa.

Chỉnh sửa 8/25: Mọi thứ trở nên khó chịu khi tôi vượt qua 25 mục, nhưng hóa ra tôi có một vấn đề nhỏ trong sắp xếp trước đã được khắc phục ngay bây giờ.

private static ITransform[] OrderTransforms(ITransform[] source) 
    { 
     return OrderTransforms(
      new List<ITransform>(source), 
      new Stack<ITransform>(), 
      new HashSet<OpCode>(source.SelectMany(transform => transform.RemovedOpCodes)), 
      source.Aggregate(InstructionSemantics.None, (preventedSemantics, transform) => preventedSemantics | transform.RemovedSemantics) 
      ); 
    } 

    private static ITransform[] OrderTransforms(List<ITransform> source, Stack<ITransform> selected, HashSet<OpCode> preventAdd, InstructionSemantics preventSemantics) 
    { 
     if (source.Count == 0 && preventAdd.Count == 0) 
      return selected.ToArray(); 

     for (int i = source.Count - 1; i >= 0; i--) 
     { 
      var transform = source[i]; 
      if ((preventSemantics & transform.InsertedSemantics) != 0) 
       continue; 

      if (preventAdd.Intersect(transform.InsertedOpCodes).Any()) 
       continue; 

      selected.Push(transform); 
      source.RemoveAt(i); 
#if true 
      var result = OrderTransforms(source, selected, new HashSet<OpCode>(preventAdd.Except(transform.RemovedOpCodes).Union(transform.PreventOpCodes)), (preventSemantics & ~transform.RemovedSemantics) | transform.PreventSemantics); 
#else // this is even slower: 
      OpCode[] toggle = preventAdd.Intersect(transform.RemovedOpCodes).Union(transform.PreventOpCodes.Except(preventAdd)).ToArray(); 
      preventAdd.SymmetricExceptWith(toggle); 
      var result = OrderTransforms(source, selected, preventAdd, (preventSemantics & ~transform.RemovedSemantics) | transform.PreventSemantics); 
      preventAdd.SymmetricExceptWith(toggle); 
#endif 
      if (result != null) 
       return result; 

      source.Insert(i, transform); 
      selected.Pop(); 
     } 

     return null; 
    } 

Trong một nỗ lực để đòi lại tiền thưởng của tôi, tôi đã giảm thời gian phân loại từ 15380s để 173ms bởi heuristically Việc chuẩn bị trước các mảng, ngay sau đó là các loại định tuyến trên.

private static ITransform[] PreSortTransforms(ITransform[] source) 
{ 
    // maps an opcode to the set of transforms that remove it 
    ILookup<OpCode, ITransform> removals = 
     source 
     .SelectMany(transform => transform.RemovedOpCodes.Select(opcode => new 
     { 
      OpCode = opcode, 
      Transform = transform 
     })) 
     .ToLookup(item => item.OpCode, item => item.Transform); 

    // maps an opcode to the set of transforms that add it 
    ILookup<OpCode, ITransform> additions = 
     source 
     .SelectMany(transform => transform.InsertedOpCodes.Select(opcode => new 
     { 
      OpCode = opcode, 
      Transform = transform 
     })) 
     .ToLookup(item => item.OpCode, item => item.Transform); 

    // maps a set of items (A) to a set of items (B), where ALL elements of B must come before SOME element of A 
    ILookup<IEnumerable<ITransform>, ITransform> weakForwardDependencies = 
     removals 
     .SelectMany(item => additions[item.Key].Select(dependency => new 
     { 
      Transform = item, 
      Dependency = dependency 
     })) 
     .ToLookup(item => item.Transform.AsEnumerable(), item => item.Dependency); 

    /* For items in the previous map where set A only had one element, "somewhat" order the 
    * elements of set B before it. The order doesn't [necessarily] hold when a key from one 
    * relationship is a member of the values of another relationship. 
    */ 
    var ordered = 
     weakForwardDependencies 
     .Where(dependencyMap => dependencyMap.Key.SingleOrDefault() != null) 
     .SelectMany(dependencyMap => dependencyMap.AsEnumerable()); 

    // Add the remaining transforms from the original array before the semi-sorted ones. 
    ITransform[] semiSorted = source.Except(ordered).Union(ordered).ToArray(); 

    return semiSorted; 
} 

Answer 2

Tôi nghĩ bạn đang nói về thuật toán đặt hàng ở đây thay vì thuật toán sắp xếp. Đó là bạn muốn tìm một thứ tự có các thuộc tính được liệt kê.

Tôi sẽ ngạc nhiên nếu thuật toán đặt hàng cụ thể đã tồn tại mà sẽ đáp ứng các thuộc tính này.

Lưu ý rằng bạn có thể không tìm được đơn đặt hàng cho một nhóm hoạt động nhất định. Thật vậy có thể thậm chí không có một phần/mạng lưới đặt hàng.Một ví dụ tầm thường là:

op1(adds(1),removes(2)) 
op2(adds(2),removes(1)) 

Answer 3

Nghe như một nút trong biểu đồ có hướng với các cạnh là các ràng buộc bạn đã đề cập.

---

Edit:@280Z28 nhận xét về câu trả lời này:

Tôi đang sử dụng một loại topo ngay bây giờ, nhưng đó là kỹ thuật quá mạnh. Tôi cần một số cách để có các nhóm "yếu" của các cạnh (một hoặc nhiều cạnh của nhóm nắm giữ trong trật tự chính thức)

Tôi không chắc tôi làm theo những gì bạn nam về yếu nhóm cạnh, nếu điều này đề cập đến các chu kỳ phá vỡ thì sắp xếp topo có thể làm điều này, cách tôi đã làm là duy trì một số trong số cho thấy số lượng unvisited nút trỏ đến nút này. Sau đó, đối với mỗi lần lặp, bạn làm việc trên một trong các nút có số lượng tối thiểu trong số, nếu số tính không bằng 0 có nghĩa là có chu kỳ và bạn tự ý phá vỡ chu kỳ này để hoàn thành việc sắp xếp.

Answer 4

Vì phần tử X có thể xuất hiện tiếp theo trong danh sách không chỉ phụ thuộc vào phần tử cuối cùng trong danh sách mà còn trên các phần tử trước, bạn có quyền nói rằng phân loại topo quá mạnh. Đây là vấn đề tìm kiếm tổng quát hơn, vì vậy tôi sẽ thử một giải pháp tổng quát hơn: tìm kiếm ngược hoặc tìm kiếm động. Trước đây luôn luôn có thể được thực hiện, nhưng đôi khi rất chậm; sau này sẽ dẫn đến một giải pháp nhanh hơn (nhưng nhiều bộ nhớ hơn), nhưng nó đòi hỏi bạn có thể tìm thấy một D.P. xây dựng vấn đề, không phải lúc nào cũng có thể.