Làm thế nào để làm mảng thưa thớt trong ca cao

Question

Tôi có một kích thước chưa xác định cho tập dữ liệu dựa trên các phím số nguyên duy nhất.

Tôi muốn sử dụng số NSMutableArray để tra cứu nhanh vì tất cả các khóa của tôi đều dựa trên số nguyên.

Tôi muốn thực hiện việc này.

NSMutableArray* data = [NSMutableArray array]; // just create with 0 size 

sau đó mọi người sau này sẽ bắt đầu ném dữ liệu tôi với chỉ số nguyên (tất cả là duy nhất) vì vậy tôi chỉ muốn làm một cái gì đó như thế này ...

if ([data count] < index) 
    [data resize:index]; // ? how do you resize 

và có mảng thay đổi kích cỡ để tôi sau đó có thể làm ...

[data insertObject:obj atIndex:index]; 

với tất cả các vị trí giữa kích thước cuối cùng và kích thước mới bằng 0 mà cuối cùng sẽ được điền sau.

Vì vậy, câu hỏi của tôi là làm cách nào để thay đổi kích thước hiện tại NSMutableArray?

Cảm ơn, La Mã

Answer 1

Nghe có vẻ như nhu cầu của bạn sẽ được đáp ứng tốt hơn với một NSMutableDictionary. Bạn sẽ cần phải quấn int s vào NSNumber đối tượng như sau:

-(void)addItem:(int)key value:(id)obj 
{ 
    [data setObject:obj forKey:[NSNumber numberWithInt:key]]; 
} 

-(id)getItem:(int)key 
{ 
    return [data objectForKey:[NSNumber numberWithInt:key]]; 
} 

Không dễ dàng là để phóng to kích thước của một NSMutableArray, vì bạn không thể có con số không đối tượng trong ở giữa khe. Tuy nhiên, bạn có thể sử dụng [NSNull null] làm 'trình điền' để tạo sự xuất hiện của một mảng thưa thớt.

Answer 2

Sử dụng NSPointerArray.

http://developer.apple.com/mac/library/documentation/Cocoa/Reference/Foundation/Classes/NSPointerArray_Class/Introduction/Introduction.html

NSPointerArray là một bộ sưu tập có thể thay đổi mô hình sau NSArray nhưng nó cũng có thể giữ các giá trị NULL, mà có thể là chèn hoặc chiết xuất (và đó góp phần count của đối tượng). Hơn nữa, không giống như các mảng truyền thống, bạn có thể đặt số đếm của mảng trực tiếp. Trong một môi trường thu thập rác thải , nếu bạn chỉ định cấu hình bộ nhớ yếu zeroing, nếu phần tử được thu thập, nó sẽ được thay thế bằng giá trị NULL.

Nếu bạn sử dụng từ điển như giải pháp, hãy sử dụng NSMapTable. Nó cho phép các phím số nguyên. Giải pháp dựa trên NSMutableDictionary được đề xuất có một số lượng lớn chi phí liên quan đến tất cả các boxing & unboxing của các phím số nguyên.

Answer 3

Tôi không đồng ý với câu trả lời của bbum về vấn đề này. Một NSPointerArray là một mảng, không phải là mảng thưa thớt và có sự khác biệt quan trọng giữa hai mảng.

I mạnh khuyên bạn không nên sử dụng giải pháp bbums.

Tài liệu cho NSPointerArray có sẵn here.

Ca cao đã có đối tượng mảng như được xác định bởi lớp NSArray. NSPointerArray được kế thừa từ NSObject, vì vậy, đây không phải là lớp con trực tiếp của NSArray. Tuy nhiên, các tài liệu NSPointerArray định nghĩa lớp như vậy:

NSPointerArray is a mutable collection modeled after NSArray but it can also hold NULL values

tôi sẽ làm cho các giả định rằng tiên đề định nghĩa này từ tài liệu khẳng định rằng đây là một "logic" lớp con của NSArray.

Definitions-

A "chung" mảng là: một bộ sưu tập các mặt hàng, mỗi trong số đó có một số chỉ số duy nhất liên kết với nó.

Một mảng, không có trình độ, là: Mảng "chung" trong đó các chỉ mục của các mục có các thuộc tính sau: Chỉ mục cho các mục trong mảng bắt đầu tại 0 và tăng tuần tự. Tất cả các mục trong mảng chứa số chỉ mục nhỏ hơn số mục trong mảng. Việc thêm một mục vào một mảng phải ở chỉ mục + 1 của mục cuối cùng trong mảng, hoặc một mục có thể được chèn vào giữa hai số chỉ mục mục hiện có khiến số chỉ mục của tất cả các mục tiếp theo được tăng thêm một. Một mục tại một số chỉ mục hiện có có thể được thay thế bằng một mục khác và thao tác này không thay đổi số chỉ mục của các hoạt động hiện có. Do đó, chèn và thay thế là hai hoạt động riêng biệt.

Mảng thưa thớt là: Mảng "chung" trong đó số chỉ mục của mục đầu tiên có thể bắt đầu ở bất kỳ số nào và số chỉ mục của các mục tiếp theo được thêm vào mảng không có liên quan hoặc hạn chế dựa trên các mục khác trong mảng. Chèn một mục vào một mảng thưa thớt không ảnh hưởng đến số chỉ mục của các mục khác trong mảng. Chèn một mục và thay thế một mục thường đồng nghĩa trong hầu hết các triển khai. Số lượng các mục trong mảng thưa thớt không có mối quan hệ với số chỉ mục của các mục trong mảng thưa thớt.

Những định nghĩa này đưa ra những dự đoán nhất định về hành vi của một mảng "hộp đen" có thể kiểm chứng. Để đơn giản, chúng tôi sẽ tập trung vào mối quan hệ sau:

Trong một mảng, số chỉ mục của tất cả các mục trong mảng nhỏ hơn số lượng mục trong mảng. Trong khi điều này có thể đúng với một mảng thưa thớt, nó không phải là một yêu cầu.

Trong một bình luận cho bbum, tôi tuyên bố như sau:

một NSPointerArray không phải là một mảng thưa thớt, cũng không cư xử như một. Bạn vẫn phải điền vào tất cả các chỉ mục chưa sử dụng với các con trỏ NULL. Output từ [pointerArray insertPointer:@"test" atIndex:17]; trên tươi instantiated NSPointerArray:

*** Terminating app due to uncaught exception 'NSInvalidArgumentException', reason: '*** -[NSConcretePointerArray insertPointer:atIndex:]: attempt to insert pointer at index 17 beyond bounds 0'

Đó là tuyên bố, mà không cần chứng minh, các hành vi của NSPointerArray trên vi phạm chính định nghĩa của một mảng thưa thớt. Phần này của thông báo lỗi được tiết lộ: attempt to insert pointer at index 17 beyond bounds 0', đặc biệt là phần về việc phải thêm mục mới đầu tiên tại chỉ số 0.

bbum sau đó bình luận:

Đó là không chính xác. Bạn không gọi được -setCount: để đặt dung lượng thành kích thước đủ.

Đó là phi sensical để "thiết lập đếm" số lượng các mục trong một mảng thưa thớt. Nếu NSPointerArray là một mảng thưa thớt, người ta sẽ mong đợi rằng sau khi thêm mục đầu tiên tại chỉ mục 17, số lượng các mục trong số NSPointerArray sẽ là một. Tuy nhiên, theo lời khuyên của bbums, số lượng mục trong số NSPointerArray sau khi thêm các mục đầu tiên là 18, chứ không phải 1.

QED- Nó được hiển thị rằng một số thực tế là một mảng và cho mục đích của cuộc thảo luận này là NSArray.

Bên cạnh đó, bbum làm cho các ý kiến ​​bổ sung sau đây:

NSPointerArray chắc chắn nhất không lỗ hỗ trợ.

Điều này là sai. Một mảng yêu cầu tất cả các mục chứa trong nó chứa một cái gì đó, ngay cả khi cái gì đó là 'không có gì'. Điều này không đúng với một mảng thưa thớt. Đây là định nghĩa của một 'lỗ hổng' cho các mục đích của cuộc thảo luận này. A NSPointerArray không chứa holes trong ý nghĩa mảng thưa thớt của cụm từ.

Đó là một trong toàn bộ các điểm viết lớp. Bạn phải đặt số đầu tiên.

Thật không hợp lý để "đặt số lượng" của mảng thưa thớt.

Cho dù triển khai nội bộ là mảng thưa thớt hay băm hay, vv, là chi tiết triển khai.

Điều này đúng. Tuy nhiên, tài liệu cho NSPointerArray không thực hiện bất kỳ tham chiếu nào đến cách nó triển khai hoặc quản lý mảng các mục của nó. Hơn nữa, nó không tuyên bố bất cứ nơi nào mà một NSPointerArray "quản lý hiệu quả một mảng con trỏ NULL."

QED- bbum là tùy thuộc vào hành vi không có giấy tờ rằng một NSPointerArray hiệu quả xử lý NULL con trỏ qua một mảng thưa thớt trong nội bộ. Là hành vi không có giấy tờ, hành vi này có thể thay đổi bất kỳ lúc nào hoặc thậm chí không áp dụng cho tất cả các lần sử dụng của NSPointerArray. Thay đổi trong hành vi này sẽ là thảm họa nếu số chỉ mục cao nhất được lưu trữ trong đó đủ lớn (~ 2^26).

Và, trên thực tế, nó không được triển khai như một bộ nhớ lớn ...

Một lần nữa, đây là một tin thực hiện chi tiết đó là không có giấy tờ. Đó là cực kỳ thực hành lập trình kém phụ thuộc vào loại hành vi này.

Answer 4

Như trong câu trả lời của Jason, NSMutableDictionary có vẻ là cách tiếp cận tốt nhất. Nó bổ sung thêm chi phí của việc chuyển đổi các giá trị chỉ mục đến và từ NSNumbers, nhưng đây là một giao dịch không gian/thời gian cổ điển tắt.

Trong triển khai của mình, tôi cũng bao gồm một NSIndexSet để thực hiện việc duyệt qua mảng thưa thớt đơn giản hơn nhiều.

Xem https://github.com/LavaSlider/DSSparseArray