On 17/05/2008, at 12:59 AM, Simen Kvaal wrote: > > What would be the most efficient way to do this? Would it depend on > the density of the array? Typically, I have ~1000 indices and ~5 bits > set. > > My present code traverses first A (using J1F and J1N on A) and using > J1T on B for each result. The result is then stored. Then, it repeats > the process on B. > > This is fast; about as fast as using bit-wise manipulations on > unsigned integers, which was my old representation of the patterns. > However, it seems to scale not so well when the largest indicex > present grows.
I have two ideas. The first depends on your insert/delete vs read frequency: maintain d(A,B), d(B,A) and the j functions directly, and modify them on insertion and deletion. The second is to use a JudyL, and store a bit pattern in the data word, i.e. use a hybrid data structure. However given your small set sizes (5) and small maximum element value, it's not clear how to improve performance algorithmically: it's likely small machine/compiler dependent quirks will play a significant role in performance. 1024 bits is 128 bytes, which is pretty close to a cache line size, so your original bit array was probably quite fast. -- john skaller [EMAIL PROTECTED] ------------------------------------------------------------------------- This SF.net email is sponsored by: Microsoft Defy all challenges. Microsoft(R) Visual Studio 2008. http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ _______________________________________________ Judy-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/judy-devel
