caching - Algorithm for Minimizing Number of Large Loads -

-

i have algorithm need compute pair-wise distances between large objects (where distance true metric, dist(a,b) == dist(b,a), among other metric requirements). have around thousand objects, need calculate 500,000 distances. there few issues:

  1. all of these 1000 objects serialized, sitting in individual files on disk.
  2. reading them disk huge operation compared relatively trivial distance calculation.
  3. i can't have of them in memory @ same time without swapping, , thrashing. can fit 500 in memory @ time.
  4. this means @ point need re-read object memory, after having read , released memory @ point previously.

so given reading disk bottleneck, , can't read in more half @ time, can think of algorithm reading , releasing these objects minimizes total number of reads?

i considered reading in first half, doing of pair-wise distances, releasing of memory , reading second half, , doing of pair-wise distances. @ point, still need distances between objects in first half , objects in second, , i'm not sure do. considered having cache that, when full, randomly chooses present object evict , reads next one, feel there has better option. considered lru, can lead behavior object required evicted on last calculation.

all-in-all, i'm kinda stuck. advice?

load points in first half. compute pairwise distances. keeping first half in memory, load points in second half 1 one, computing distances. load entire second half , compute pairwise distances. 1.5 reads per point, optimal in following model.

the model syntactically correct program task sequence of instructions of form load(i, j), meaning load point i memory location j. program correct if, every pair of points, there exists instruction after both points in memory.

it clear that, in correct program, every point loaded @ least once. assuming 1000 points , 500 locations, follows there @ least 500 evictions in favor of points being loaded first time. assume without loss of generality no point ever duplicated in memory. after point p evicted in favor of point q being loaded first time, necessary reload p in order distance between p , q computed. therefore, there @ least 500 reloads , hence @ least 1500 loads.


Comments

Post a Comment

Popular posts from this blog

java - activate/deactivate sonar maven plugin by profile? -

-
i use sonar plugin executes if activated in maven profile. sonar runs on every compile. the problem build fail other team members not have sonar application installed locally. pom.xml checked in team members same copy including sonar configuration, don't want them modify purpose of disabling sonar (they might inadvertently check modified copy in). please advise how configure maven (.m2/settings.xml) and/or pom.xml sonar feature can enabled/disabled local profile. here sonar configuration in each project's pom.xml: <plugin> <groupid>org.codehaus.mojo</groupid> <artifactid>sonar-maven-plugin</artifactid> <version>1.0</version> <executions> <execution> <id>make-sonar</id> <phase>compile</phase> <goals> <goal>sonar</goal> </goals> </execution> </executions> ...
Read more

python - TypeError: can only concatenate tuple (not "float") to tuple -

-
i'm new python, question might easy, anyway, patience: as trying call newton-raphson method calculate implied volatility in black-scholes formula call/put option pricing, first thing is, newton method in scipy.optimize seems calculate function's zeros, in black-scholes formula, want function's value option price, not zero. (i'm new here programming, i'm not sure techniques.) should write function things like: def f(sigma, price): return bsformula(s0,k,r,t,q,sigma) - price then, while calling newton method, takes args=() 1 parameter in function, write this: value = newton(bsprice2, 0.5, args=price) but error message: file "bs.py", line 36, in bsimpvol value = newton(bsprice2, 0.5, args=float(price)) file "/usr/lib/python2.7/dist-packages/scipy/optimize/zeros.py", line 143, in newton q0 = func(*((p0,) + args)) typeerror: can concatenate tuple (not "float") tuple could tell me why that? how fix it? apprecia...
Read more

java - What is the difference between String. and String.this. ? -

-
this question has answer here: meaning of .this , .class in java 2 answers i'll straight point. im still learning bit of syntax , want know difference between code is code a: public class buttonz extends jbutton{ public buttonz(){ settext(new string(string.valueof(i))); } } please ignore fact i undeclared, not lost. code b: public class buttonz extends jbutton{ public buttonz(){ settext(new string(string.this.charat(i))); } } what don't yet understand difference in typing string.this , string. i under assumption when use dot operator on class accessing it's static methods(and/or variables if they're not hidden). i have studied little bit , have concluded when using string. accessing string static methods.. when using string.this. i'm accessing methods class buttonz extendi...
Read more