Re: Storm in a water glass? (Was: Table View Blues (summary))

FROM : Nat!
DATE : Sat Nov 23 00:19:18 2002

Am Donnerstag, 21.11.02 um 22:22 Uhr schrieb Rixster @ Rixstep:

>> (Aaron, there should be a Download link on the book page... if
>> there is, I can't find it.. )
>
> I'm sure Aaron can.
>
>> Also... using the methodology that you've used, you're doing 4
>> times as many searches for objects as necessary in the deletion
> because
>> you're using 4 times as many rows.
>
> 10,000 is not a magic number.
>
>> And, as I've said, deletion in a background thread would be an
>> option if deletion is what you're seriously concerned about.
>
> And what, pray tell, is the foreground thread running the GUI to do
> in the meantime? Are we going to start adding new records before the
> old ones are deleted??!??
>
>> And still, deleting 40,000 items in the manner you are, isn't the
>> same method that would be used to switch to another view or close
> a
>> tableview.
>
> But it is the method that would be used to delete 40,000 items.
>

Well the problem with this is that Foundations implementation of
removeObjectsInArray is surprisingly (...) unsophisticated.
If you have an array and want to remove an object from it in the
average case the entry removal routine will check half the records
until it finds the entry and delete it. Then it will do the same with
the next entry to remove.

In your case thats 10000 records to remove from 40000. That means it
will have to do ca. 20000 * 10000 compares. (*1*) That's 200 Million
compares!

You need to use a more clever approach to remove many objects from a
large array.

---
As I happen to enjoy coding a few line of Objective-C after a day of C#
here's some code quickly hacked together . Gets the job done in about a
second or so, and it really isnt optimized either :)


#import <Foundation/Foundation.h>

@interface NSMutableArray ( FastRemove)

- (void) removeManyObjectsInArray:(NSArray *) array;

@end

@implementation NSMutableArray ( FastRemove)

- (void) removeManyObjectsInArray:(NSArray *) array
{
    NSHashTable      *lut;
    IMP              impObjectAtIndex;
    NSMutableArray  *copy;
    unsigned int    m;
    unsigned int    n;
    unsigned int    i;
    id              p;

    n = [array count];
    m = [self count];

    /* -- if u like --
    if( n < 16 || m < 16 || n * m < 1024)  // guessed values where
copying does not pay off
    {
      [self removeObjectsInArray:array];
      return;
    }
    */

    lut = NSCreateHashTable( NSNonRetainedObjectHashCallBacks, n);
    for( i = 0; i < n; i++)
      NSHashInsertIfAbsent( lut, [array objectAtIndex:i]);

    copy = [NSMutableArray arrayWithCapacity:m];
    for( i = 0; i < m; i++)
    {
      p = [self objectAtIndex:i];
      if( ! NSHashGet( lut, p))
          [copy addObject:p];
    }
    NSFreeHashTable( lut);

    [self setArray:copy];
}

@end

#define N_ARRAY        40000


int main (int argc, const char *argv[])
{
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    NSMutableArray    *array;
    NSMutableArray    *removers;
    NSString          *s;
    unsigned int      i;


    array    = [NSMutableArray array];
    removers = [NSMutableArray array];
    for( i = 0; i < N_ARRAY; i++)
    {
      s = [NSString stringWithFormat:@"XXX-#%d", i];
      [array addObject:s];
      if( (i & 3) == 0)
      {
          s = [NSString stringWithFormat:@"XXX-#%d", N_ARRAY - 1 - i];
          [removers addObject:s];
      }
    }

    NSLog( @"Start: %u %u", [array count], [removers count]);
    [array removeManyObjectsInArray:removers];
    NSLog( @"End: %u %u", [array count], [removers count]);

/*
    array    = [NSMutableArray array];
    removers = [NSMutableArray array];
    for( i = 0; i < N_ARRAY; i++)
    {
      s = [NSString stringWithFormat:@"XXX-#%d", i];
      [array addObject:s];
      if( (i & 3) == 0)
      {
          s = [NSString stringWithFormat:@"XXX-#%d", N_ARRAY - 1 - i];
          [removers addObject:s];
      }
    }

    NSLog( @"Start: %u %u", [array count], [removers count]);
    [array removeObjectsInArray:removers];
    NSLog( @"End: %u %u", [array count], [removers count]);
  */

    [pool release];
    return 0;      // ...and make main fit the ANSI spec.
}

Ciao
   Nat!

(*1*) actually its less, because both arrays shrink. My estimation
would be half (100 Mio.) but I am no mathematician :)
------------------------------------------------------
I was hoping that the people of the world might be
united by something more interesting, like drugs or
an armed struggle against the undead. Unfortunately my
father's team won, so computers it is. -- Sedaris
_______________________________________________
cocoa-dev mailing list | <email_removed>
Help/Unsubscribe/Archives: http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.