Karim Belabas on Thu, 20 Nov 2014 21:38:51 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Growing ordered set |
* Charles Greathouse [2014-11-20 19:42]: > Fairly often I have a problem of the type 'generate a number by a given > process, and repeat until a duplicate is found'. I also have the related > problem 'generate a number by a given process, and repeat until some limit, > recording the number of distinct elements at each step'. > > What's a good way to go about this in GP? I don't see any generic way in GP. I'd throw the required 3 lines in a C file using our generic hashtables and install it with a simple wrapper... // generic hash table of initial size 100, allocated on stack; keys are GENs hashtable *h = hash_create(100, &hash_GEN, &gidentical, 1); // if key k not present, insert (arbitrary) NULL as associated value if (!hash_search(h, (void*)k)) hash_insert(h, (void*)k, NULL); (can be made more efficient by implementing a trivial routine fusing the last two steps) There are three main reasons we can't export this in GP without major nightmares : 1) struct hashtable is not a GEN, and neither are its components; it doesn't fit the memory model (gerepile, etc.). 2) there'd be no way to handle this in a "safe" way in GP without deep copies all around, making the mechanism much less efficient than it should. The current implementation uses only pointers and assumes keys/values are permanent. 3) GP2C Cheers, K.B. P.S. The way I usually work around such problems is by having a global variable in a C file corresponding to the unique instance of the C struct I want to handle, and add simple GP-friendly methods with GEN arguments / return values, which are allowed to manipulate that private data. I have a working interface to IBM/Ilog CPLEX for instance: 2 globals CPXENVptr / CPXLPptr, and a few exported methods init/add_constraint/add_objective, minimize/maximize, set variable type [real/integer], etc. The whole thing is about 230 lines of C code and allows me to drive huge linear programs through GP. If you want multiple instances of that foreign class, then you store then in a table, thereby indexing them by small integers, and pass the integer key as an extra argument (specifying the affected instance) via your GP functions. And of course you must make everything orthogonal to GP/PARI stack and garbage collections ! -- Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 Universite de Bordeaux Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux1.fr/~kbelabas/ F-33405 Talence (France) http://pari.math.u-bordeaux1.fr/ [PARI/GP] `