问:
What is the correct way to publish a runtime? Should it be a singleton?
I have a compiler for a programming language that targets JavaScript. That language needs some global functions such as: alloc, memcpy, write and so on. My question is: where should I position those functions? I have pretty much 2 options:

1: inside a self-contained object, runtime. Compiled functions would need to receive that object:

```<code>function example_of_compiled_function(runtime, arg0, arg1){
    var arrayPtr = runtime.alloc(arg0);
    for (var i=0; i<arg0; ++i)
        runtime.write(arrayPtr+i, arg1);
    return arrayPtr;
};
</code>```

2: globally. Compiled functions wouldn't need to receive an additional object:

```<code>function example_of_compiled_function(arg0, arg1){
    var arrayPtr = alloc(arg0);
    for (var i=0; i<arg0; ++i)
        write(arrayPtr+i, arg1);
    return arrayPtr;
}
</code>```

Both ways have problems. For (1), there is a considerable slowdown for accessing methods inside an object, and using compiled functions becomes more complicated since users have to manually create that object and feed it to them. For (2), it is faster and simpler, but might pollute the global namespace. Is there a satisfactory solution for this?

答:
How about putting runtime in a closure?

```<code>function mycode(runtime) {
   function example_of_compiled_function(arg0, arg1){
    var arrayPtr = runtime.alloc(arg0);
    for (var i=0; i<arg0; ++i)
        runtime.write(arrayPtr+i, arg1);
    return arrayPtr;
   }
};
</code>```

Simply pass in runtime to this function (or any further generated functions), and it'll be accessible to all code in the closure without explicitly passing it everywhere.

Body:
How about putting runtime in a closure?

function mycode(runtime) {
   function example_of_compiled_function(arg0, arg1){
    var arrayPtr = runtime.alloc(arg0);
    for (var i=0; i<arg0; ++i)
        runtime.write(arrayPtr+i, arg1);
    return arrayPtr;
   }
};

Simply pass in runtime to this function (or any further generated functions), and it'll be accessible to all code in the closure without explicitly passing it everywhere.


问:
A 'task' system which has an ending, to get ready for next task
I want to make a system, so that there are certain tasks. For example, let's talk about a game. I want to make it so there are 100+ tasks doing different things, but when the player's magic level is 5, it will do the magic task, if the player's fighting skill is level 5, it will fight. I have that already, however here is the catch. I want to make it so once the task executes, it will have an 'ending'. So, it will do something before it finally gets killed.

My code so far:

```<code>for (GameTask a : s.gameTasks) {
    if (a != null) {
        if (a.validate()) {
            a.execute();
        }
    }
}
</code>```

It will loop all the tasks and execute them, however how can I implement an 'ending' to it, so that it will get ready for the next task? I hope I have written it clearly as English is not my first language.

tl;dr, I want to add an 'end' to each task so that it can be killed and can be ready for next task.

答:
Is each GameTask less like a "task" and more like a "process"? Usually I think of a task as doing one thing and then stopping. It's just one step in a larger process. If you want to add more than one step to your GameTasks, then they become like little processes.

There are lots of different ways to address this, but one idea is to make each GameTask into a finite state machine -- that is, the "task" is in some state, and takes one step each round, and (maybe) transitions to a new state. When it finally gets to the terminal state, it can just fall out of the list.

(That's a really common way to handle independently running objects in game programming, but there are other ways to do it -- like when the task executes, it pushes itself or a new task onto the list for the next round.)

ContentLicense: CC BY-SA 3.0


问:
How do you respond to a request for 'emergency contact information' for when you are on vacation?
I want to go on vacation and not think about work at all but they want me to provide them a contact number in the event of an emergency (server goes down, web service malfunctions, etc). I am afraid that it will be abused (they will contact me before trying everything for example) but I also think that if I am on vacation I should not be bothered even if there is an outage. Does anyone have experience with situations like this? What's the tactful approach? Any creative solutions?</p>

答:
Back in the day we used to get "pager pay" if we were to be on call.  You could try "clarifying" whether that's whether what they're offering. Then, assuming they just  want you to offer to have your vacation interrupted for free, tell them you will check your voice mail (on your cell, at the hotel message centre, or at home) each night, or once a week, or whatever you feel like offering, and give them that number.

There are times it's handy to go on vacation into the wilderness (no cell signal) or to a country where your cell phone doesn't work.

ContentLicense: CC BY-SA 2.5


问:
Range of values based on key values
I'm trying to implement a method of searching trough a large amount of 2D points for those that match a certain range. I'm thinking of creating HashMaps for <X, Point> and <Y, Point> but I'm wondering is HashMap good for doing this, because I will be taking points in a range, based on values from x_min to x_max and y_min to y_max.

So I will basically take all points from <X,Point> searching from x_min to x_max and compare them to points taken from <Y,Point> from y_min to y_max...

```<code>HashMap<Integer,Point> x_coordinates = new HashMap<Integer,Point>();
for(int i=x_min;i<=x_max;i++){
    if(x_coordinates.containsKey(i))
        x_coordinates.get(i);
}

HashMap<Integer,Point> y_coordinates = new HashMap<Integer,Point>();
for(int i=y_min;i<=y_max;i++){
    if(y_coordinates.containsKey(i))
         y_coordinates.get(i);
}
</code>```

Is there a faster way to get a range of values from a HashMap, or some other type of data structure?

For example, if range = 200, select all points that match the range from x-200 to x+200 and from y-200 to y+200

I'm trying to avoid iteration through all of the points, but also I want to avoid making a huge 2D matrix, because the points in question are scattered around a large area.

After some testing and based on MichaelT's answer, I've written this code:

```<code>TreeMap<Integer, TreeMap<Integer, Integer>> values;
for (int x : values.subMap(x_min, x_max).keySet()) {
        for (int y : values.get(x).subMap(y_min, y_max).values()) {
            // y here, represents the values of points in range...
        }
    }
</code>```

答: While your solution based on a treemap of treemaps will work, and is much better than the hashmap solution you started with, you may want to look into the possibility of using a QuadTree, which is a structure similar to a TreeMap but with a pair of coordinates as the key rather than just one. This makes selecting rectangular ranges from them particularly efficient. There are many implementations available for Java that can be found with a quick google.</p>

Title: Range of values based on key values


问:
Using higher order functions to apply m out of M filter's and then transform data of size n?
Total no: of filters possible is M . User can select m filters where m <= M . A typical example is files from a folder , he could say modified between so and so date , start with so and so and so on.

```<code>meets = []
for each in something:
    if user_filter1:
       if user_filter1_condition_met:
          meets.append(True)
    #hardcode all other filters here
    if all(meets):
          do_something(each)

    else:
       meets = True
       for each in something:
           do_something(each)
</code>```

Here I am repeating the entire code again which is against DRY principles.

```<code>for each in something:
    if user_filter:
       if not filter_condition_met:
          continue
    do_something(each)
</code>```

Here I am doing the filter check for all items in the loop, while essentially it needs to be done just once.

Can I use higher order functions to check the filter condition once and generate a code that does the job? It looks like a filter and then transform operation. Can someone give some ideas?

An addendum to the question with a similar essence:

```<code>def function(inner,outer):
      for each in outer:
           for each in inner:
                 print "Something"

#Border condition inner doesn't exist I need a code object that goes like this:

def function(inner,outer):
      for each in outer:
           print "Something"

#Inner doesn't exist , so I want to to not go a for each in inner operation i.
#I mean it won't change the complexity of the problem at hand
#But suppose there are billions elements , I save billion for each in [].
</code>```

答:
Conceptually, each filter is a predicate - a function that given an input, returns either true or false. The python function filter(function, iterable) accepts a predicate and an iterable, and returns only items that the predicate is true for. So what you want is a way to combine all the filters a user selects into one filter, that only matches if all of them match. The all function can be used here, all(iterable) returns true only if every element of iterable is true. Using this, we can combine predicates:

```<code>def andPredicate(predicates):
    def pred(v):
        return all((p(v) for p in predicates))
    return pred
</code>```

The andPredicates function accepts a list of predicates and gives you a new one that only returns true for an item if all the predicates return true for that item. For example, if you have predicates isNumber and isLessThanZero, you can define isNegativeNumber like this:

```<code>isNegativeNumber = andPredicate([isNumber, isLessThanZero])
print(isNegativeNumber("foo")) # False
print(isNegativeNumber(8)) # False
print(isNegativeNumber(-5)) # True
</code>```

So this lets you combine filters. If you have a list of filters, where each filter is a predicate, then you can just do this:

```<code>filteredItems = filter(andPredicate(userFilters), items)
</code>```

Done and done. The iterable is only iterated once, and the filters are checked one at a time on an item until one fails. If one fails, the rest of the filters are skipped and the next item is taken, if they all succeed, then the item is included in the final iterable. Note that filter produces a list in Python 2.x and an iterator in Python 3.x.

Additionally, the definition of andPredicates can be further shortened with an anonymous function, but that may be unclear to readers of your code if they're not familiar with functional programming patterns:

```<code>def andPredicate(predicates):
    return lambda v: all((p(v) for p in predicates))
</code>```

For completeness, here are definitions of the aforementioned isNumber and isLessThanZero predicates:

```<code>from numbers import Number

def isNumber(v):
    return isinstance(v, Number)

def isLessThanZero(x):
    return x < 0
</code>```

In the second part of your question, you want to either do something once for each item in the cross product of two lists, or you want to do something once for each item in the second list of the first list is empty. The itertools module contains a function product that basically does the same thing as nested for loops. For instance instead of this:

```<code>for a in as:
    for b in bs:
        print("Something!")
</code>```

You can write this:

```<code>from itertools import product

for a, b in product(as, bs):
    print("Something!")
</code>```

Both pieces of code are equivalent. When one of the iterables is empty however, the whole product is empty, just like in nested for loops. We can write our own version of product that instead of being empty when one of the iterables is empty, is only empty when both are empty and if just one is empty, then it just returns the values in the other iterable and uses None as the values for the first iterable. This can be defined like so:

```<code>from itertools import product

def productWithNones(as, bs):
    if as and bs:
        return product(as, bs)
    if as:
        return product(as, [None])
    if bs:
        return product([None], bs)
    return []
</code>```

Now this:

```<code>for a, b in productWithNones([1, 2, 3], []):
    print((a, b))
</code>```

Prints this:

```<code>(1, None)
(2, None)
(3, None)
</code>```

Instead of simply being empty. So your original loop can be written as:

```<code>isNegativeNumber = andPredicate([isNumber, isLessThanZero])
print(isNegativeNumber("foo")) # False
print(isNegativeNumber(8)) # False
print(isNegativeNumber(-5)) # True
</code>```0

Body:
Conceptually, each filter is a predicate - a function that given an input, returns either true or false. The python function filter(function, iterable) accepts a predicate and an iterable, and returns only items that the predicate is true for. So what you want is a way to combine all the filters a user selects into one filter, that only matches if all of them match. The all function can be used here, all(iterable) returns true only if every element of iterable is true. Using this, we can combine predicates:

def andPredicate(predicates):
    def pred(v):
        return all((p(v) for p in predicates))
    return pred

The andPredicates function accepts a list of predicates and gives you a new one that only returns true for an item if all the predicates return true for that item. For example, if you have predicates isNumber and isLessThanZero, you can define isNegativeNumber like this:

isNegativeNumber = andPredicate([isNumber, isLessThanZero])
print(isNegativeNumber("foo")) # False
print(isNegativeNumber(8)) # False
print(isNegativeNumber(-5)) # True

So this lets you combine filters. If you have a list of filters, where each filter is a predicate, then you can just do this:

filteredItems = filter(andPredicate(userFilters), items)

Done and done. The iterable is only iterated once, and the filters are checked one at a time on an item until one fails. If one fails, the rest of the filters are skipped and the next item is taken, if they all succeed, then the item is included in the final iterable. Note that filter produces a list in Python 2.x and an iterator in Python 3.x.

Additionally, the definition of andPredicates can be further shortened with an anonymous function, but that may be unclear to readers of your code if they're not familiar with functional programming patterns:

def andPredicate(predicates):
    return lambda v: all((p(v) for p in predicates))

For completeness, here are definitions of the aforementioned isNumber and isLessThanZero predicates:

from numbers import Number

def isNumber(v):
    return isinstance(v, Number)

def isLessThanZero(x):
    return x < 0

In the second part of your question, you want to either do something once for each item in the cross product of two lists, or you want to do something once for each item in the second list of the first list is empty. The itertools module contains a function product that basically does the same thing as nested for loops. For instance instead of this:

for a in as:
    for b in bs:
        print("Something!")

You can write this:

from itertools import product

for a, b in product(as, bs):
    print("Something!")

Both pieces of code are equivalent. When one of the iterables is empty however, the whole product is empty, just like in nested for loops. We can write our own version of product that instead of being empty when one of the iterables is empty, is only empty when both are empty and if just one is empty, then it just returns the values in the other iterable and uses None as the values for the first iterable. This can be defined like so:

from itertools import product

def productWithNones(as, bs):
    if as and bs:
        return product(as, bs)
    if as:
        return product(as, [None])
    if bs:
        return product([None], bs)
    return []

Now this:

for a, b in productWithNones([1, 2, 3], []):
    print((a, b))

Prints this:

(1, None)
(2, None)
(3, None)

Instead of simply being empty. So your original loop can be written as:

for eachOuter, eachInner in productWithNones(outer, inner):
    print("Something!")


问:
What is different between the internal design of Java and C++ that lets C++ have multiple inheritance?
It's drilled into the newbie Java programmers that Java (pre-Java 8) has no multiple class inheritance, and only multiple interface inheritance, because otherwise you run into diamond inheritance problem (Class A inherits from classes B and C, both of which implement method X. So which of those classes' implementation is used when you do a.X() call?)

Clearly, C++ successfully addressed this, since it has multiple inheritance.

What's different between the internal design of Java and C++ - (i'm guessing in the method dispatch methodology, and vaguely recall that it had to do with vtables from my long-ago computer languages class) that allows this problem to be solved in C++ but prevents in Java?

To rephrase:

What is the methodology of the language design/implementation used in C++ to avoid the ambiguity of diamond inheritance problem, and why couldn't the same methodology be used in Java?

答:
I might be misreading your question, but I'll give it a go, because I suspect it is a question I also had at one point.

It might look like Java doesn't have multiple implementation inheritance because it's hard to implement, while C++ has because its implementors found a way to implement it. This isn't the case. As others have said, it was a deliberate design decision to avoid a category of programming problems, not something to enable easier implementation of Java.

The very fact that Java has mulitple inheritance from interfaces means that its implementors have done the hard work of implementing multiple inheritance anyway - the fact that interfaces are abstract is mostly irrelevant.

In an implementation using vtables, to implement polymorphism under single inheritance, you need a vtable of the runtime type of your instance, perferably at a predetermined position. To implement polymorphism under multiple inheritance, you need multiple vtables.

For ease, let's say that each type's memory layout starts with its vtable (it's not required to be like this, but it'll make my description easier).

```<code>Type A [vtableA, mem1, mem2, ...]
Type B [vtableB, mem3, mem4, ...]
Type C : A, B [vtableA, mem1, mem2, ..., vtableB, mem3, mem4,...]
C* from C     ^
</code>```

Under single inheritance, you just pass the object reference around and you can always find the vtable of its runtime type.

```<code>Type C : A, B [vtableA, mem1, mem2, ..., vtableB, mem3, mem4,...]
A* from C     ^
</code>```

Under multiple inheritance, in order to use substitution, you have to pass a reference such that, if interpretreted as a reference to an instance of a supertype, it will still work. This means that the reference should point to another vtable in the memory layout of the whole instance. This is simply done by adding an offset, until the new reference points to the new vtable. This offset is known at compile time, and it's probably the total size of the preceding data in the layout.

```<code>Type C : A, B [vtableA, mem1, mem2, ..., vtableB, mem3, mem4,...]
B* from C                                ^
              <----memory size of A---->
</code>```

Notice that in the schematics I used "type", not "class". If you assume that the language doesn't allow you to declare your own data members, all the above still holds. The only difference is that Type B will now consist of only a vtable (because the language won't allow mem3, mem4, etc). But the mechanism is the same.

Body:
I might be misreading your question, but I'll give it a go, because I suspect it is a question I also had at one point.

It might look like Java doesn't have multiple implementation inheritance because it's hard to implement, while C++ has because its implementors found a way to implement it. This isn't the case. As others have said, it was a deliberate design decision to avoid a category of programming problems, not something to enable easier implementation of Java.

The very fact that Java has mulitple inheritance from interfaces means that its implementors have done the hard work of implementing multiple inheritance anyway - the fact that interfaces are abstract is mostly irrelevant.

In an implementation using vtables, to implement polymorphism under single inheritance, you need a vtable of the runtime type of your instance, perferably at a predetermined position. To implement polymorphism under multiple inheritance, you need multiple vtables.

For ease, let's say that each type's memory layout starts with its vtable (it's not required to be like this, but it'll make my description easier).

Type A [vtableA, mem1, mem2, ...]
Type B [vtableB, mem3, mem4, ...]
Type C : A, B [vtableA, mem1, mem2, ..., vtableB, mem3, mem4,...]
C* from C     ^

Under single inheritance, you just pass the object reference around and you can always find the vtable of its runtime type.

Type C : A, B [vtableA, mem1, mem2, ..., vtableB, mem3, mem4,...]
A* from C     ^

Under multiple inheritance, in order to use substitution, you have to pass a reference such that, if interpretreted as a reference to an instance of a supertype, it will still work. This means that the reference should point to another vtable in the memory layout of the whole instance. This is simply done by adding an offset, until the new reference points to the new vtable. This offset is known at compile time, and it's probably the total size of the preceding data in the layout.

Type C : A, B [vtableA, mem1, mem2, ..., vtableB, mem3, mem4,...]
B* from C                                ^
              <----memory size of A---->

Notice that in the schematics I used "type", not "class". If you assume that the language doesn't allow you to declare your own data members, all the above still holds. The only difference is that Type B will now consist of only a vtable (because the language won't allow mem3, mem4, etc). But the mechanism is the same.


答:
Instead of two hash of coordinates, you may use a list of Point2D and iterate through it.
And extract a filtered List than you can
That way, only one loop is done.

```<code>    int distance = 200;
    Point2D.Double refPoint = new Point2D.Double(0,0);

    List<Point2D.Double> pointstoSearch = new ArrayList<Point2D.Double>();
    List<Point2D.Double> filtered = new ArrayList<Point2D.Double>();
    List<Point2D.Double> POIs = new ArrayList<Point2D.Double>();
    POIs.add(new Point2D.Double(99d,100d));
    POIs.add(new Point2D.Double(101.8, 202.3));
    POIs.add(new Point2D.Double(-50, -98));

    //filtering
    for (Point2D.Double point : POIs) {
       if (point.distance(refPoint)<= distance) filtered.add(point);
    }

    //now search only the matching points//filtering
    for (Point2D.Double poi : filtered) {
        for (Point2D.Double point : pointstoSearch) {
            if (poi.equals(point)) //match
        }
    }
</code>```

For maximum efficiency, and if the map of searched coordinates (POI in my sample) is ~constant, you should consider using a quadtree structure.

Title: Range of values based on key values

Body:
I'm trying to implement a method of searching trough a large amount of 2D points for those that match a certain range. I'm thinking of creating HashMaps for <X, Point> and <Y, Point> but I'm wondering is HashMap good for doing this, because I will be taking points in a range, based on values from x_min to x_max and y_min to y_max.

So I will basically take all points from <X,Point> searching from x_min to x_max and compare them to points taken from <Y,Point> from y_min to y_max...

```<code>HashMap<Integer,Point> x_coordinates = new HashMap<Integer,Point>();
for(int i=x_min;i<=x_max;i++){
    if(x_coordinates.containsKey(i))
        x_coordinates.get(i);
}

HashMap<Integer,Point> y_coordinates = new HashMap<Integer,Point>();
for(int i=y_min;i<=y_max;i++){
    if(y_coordinates.containsKey(i))
         y_coordinates.get(i);
}
</code>```

Is there a faster way to get a range of values from a HashMap, or some other type of data structure?

For example, if range = 200, select all points that match the range from x-200 to x+200 and from y-200 to y+200

I'm trying to avoid iteration through all of the points, but also I want to avoid making a huge 2D matrix, because the points in question are scattered around a large area.

After some testing and based on MichaelT's answer, I've written this code:

```<code>TreeMap<Integer, TreeMap<Integer, Integer>> values;
for (int x : values.subMap(x_min, x_max).keySet()) {
        for (int y : values.get(x).subMap(y_min, y_max).values()) {
            // y here, represents the values of points in range...
        }
    }
</code>```

Body:
Instead of two hash of coordinates, you may use a list of Point2D and iterate through it.
And extract a filtered List than you can
That way, only one loop is done.

    int distance = 200;
    Point2D.Double refPoint = new Point2D.Double(0,0);

    List<Point2D.Double> pointstoSearch = new ArrayList<Point2D.Double>();
    List<Point2D.Double> filtered = new ArrayList<Point2D.Double>();
    List<Point2D.Double> POIs = new ArrayList<Point2D.Double>();
    POIs.add(new Point2D.Double(99d,100d));
    POIs.add(new Point2D.Double(101.8, 202.3));
    POIs.add(new Point2D.Double(-50, -98));

    //filtering
    for (Point2D.Double point : POIs) {
       if (point.distance(refPoint)<= distance) filtered.add(point);
    }

    //now search only the matching points//filtering
    for (Point2D.Double poi : filtered) {
        for (Point2D.Double point : pointstoSearch) {
            if (poi.equals(point)) //match
        }
    }

For maximum efficiency, and if the map of searched coordinates (POI in my sample) is ~constant, you should consider using a quadtree structure.


答:
As others have said I will question if C++ successfully addressed multiple inheritance.

(The only language I have seen that I consider successfully addressed multiple inheritance is Eiffel, but as we are not all using it, it is questionable if it was successfully.    I expect that most programmers will find the way it does multiple inheritance too hard to learn as it takes more than 10 minutes thinking to understand it.)

However back to Java (and C#), in both cases it was a requirement that classes could be loaded at run time.   And there is no known why to efficiently implement multiple inheritances if classes can be dynamically loaded.

I recall from  the time when Java come out that this was the most common reason given by the people working on it in talks.

Title: What is different between the internal design of Java and C++ that lets C++ have multiple inheritance?

Body:
It's drilled into the newbie Java programmers that Java (pre-Java 8) has no multiple class inheritance, and only multiple interface inheritance, because otherwise you run into diamond inheritance problem (Class A inherits from classes B and C, both of which implement method X. So which of those classes' implementation is used when you do a.X() call?)

Clearly, C++ successfully addressed this, since it has multiple inheritance.

What's different between the internal design of Java and C++ - (i'm guessing in the method dispatch methodology, and vaguely recall that it had to do with vtables from my long-ago computer languages class) that allows this problem to be solved in C++ but prevents in Java?

To rephrase:

What is the methodology of the language design/implementation used in C++ to avoid the ambiguity of diamond inheritance problem, and why couldn't the same methodology be used in Java?


问:
Generic delegates (C#) in Scala?
I wanted to know if there is an equivalent of the C# generic delegates in Scala.

The reference website is: http://msdn.microsoft.com/en-us/library/dd233060.aspx

I'm trying to make a complete comparison between C# and Scala, about (co)(contra)(in)variance.

答:
Scala doesn't have delegates, but you are free to assign functions/lambdas to variables. Here, normal subtyping rules apply. A function f: A => B is a subtype of g: C => D if the argument is a supertype A > C (contravariance) and the return type is a subtype B < D (contravariance). Note that any of those four types might actually be tuples, so that tuple subtyping will be applied in such cases.

Example:

// two (sub-)types to demonstrate variance
class A()
class B() extends A

var delegate: Option[B => A] = None

// a few simple lambdas that can be assigned
delegate = Some((b: B) => new A())  // invariant
delegate = Some((b: B) => new B())  // return type covariance
delegate = Some((a: A) => new A())  // argument type contravariance
delegate = Some((a: A) => new B())  // co- and contravariance

// can we assign methods to function types? Yes!
class Context(retVal: A) {
    def meth(b: B): A = retVal
}

val ctx = new Context(new A())
delegate = Some(ctx.meth _)  // partial application
delegate = Some(b => ctx.meth(b)) // wrapping in lambda
```

If we add (more) generics, this doesn't change anything since functions already are generic types in Scala. In particular, co- and contravariance for functions is available because functions are actually defined as trait Function1[-T1, +R]. User-defined types can also make use of variance when defined properly.

Title: Generic delegates (C#) in Scala?

Body:
Scala doesn't have delegates, but you are free to assign functions/lambdas to variables. Here, normal subtyping rules apply. A function f: A => B is a subtype of g: C => D if the argument is a supertype A > C (contravariance) and the return type is a subtype B < D (contravariance). Note that any of those four types might actually be tuples, so that tuple subtyping will be applied in such cases.

Example:

// two (sub-)types to demonstrate variance
class A()
class B() extends A

var delegate: Option[B => A] = None

// a few simple lambdas that can be assigned
delegate = Some((b: B) => new A())  // invariant
delegate = Some((b: B) => new B())  // return type covariance
delegate = Some((a: A) => new A())  // argument type contravariance
delegate = Some((a: A) => new B())  // co- and contravariance

// can we assign methods to function types? Yes!
class Context(retVal: A) {
    def meth(b: B): A = retVal
}

val ctx = new Context(new A())
delegate = Some(ctx.meth _)  // partial application
delegate = Some(b => ctx.meth(b)) // wrapping in lambda

If we add (more) generics, this doesn't change anything since functions already are generic types in Scala. In particular, co- and contravariance for functions is available because functions are actually defined as trait Function1[-T1, +R]. User-defined types can also make use of variance when defined properly.


问:
Mutating Programming Language?
For fun I was thinking about how a programming paradigm could differ from OOP and came up with this concept. I don't have a strong foundation in computer science so it might be common place without me knowing it (more likely it's just a stupid idea :)

I apologize in advance for this somewhat rambling question, anyways here goes:

In normal OOP methods and classes are variant only upon parameters, meaning if two different classes/methods call the same method they get the same output.

My,  perhaps crazy idea, is that the calling  method and class could be an "invisible" part of it's signature and the response could vary depending on who call's an method.

Say that we have a Window object with a Break() method, now anyone (who has access) could call this method on Window with the same result.

Now say that we have two different objects, Hammer and SledgeHammer. If Break need to produce different results based on these we'd pass them  as parameters  Break(IBluntObject bluntObject)

With a mutating programming language (mpl)  the operating objects on the method would be visible to the Break Method without begin explicitly defined and it could adopt itself based on them). So if SledgeHammer calls Window.Break() it would generate vastly different results than if Hammer did so.

If classes are black boxes then mutating classes are black boxes that knows who's (trying) to push it's buttons and can adapt their behavior accordingly.

You could also have different permission sets on methods depending who's calling them rather than having absolute permissions like public and private.

Does this have any advantage over OOP? Or perhaps I should say, would it add anything to it since you should be able to simply add this aspect to methods  (just give access to a CallingMethod and CallingClass variable in context)

I'm not sure, might be to hard to wrap one's head around, it would be kinda interesting to have classes that adopted themselves to who uses them though.
Still it's an interesting concept, what do you think, is it viable?

Here's some potential dummy code from a game where a player has is damaged by something. In normal OOP most things would instead be passed as parameters to the method whereas here Damage "pulls" the properties it uses. Different? yes, better? perhaps not :)

```<code>Class Player
{
    [AccessableBy:Terrain,Player]
    void Damage
    {
        if (#CallingClass has property HitPoints)
        {
            this.health -= #CallingClass.HitPoints;
        }

        if (this.health < 0 && #CallingClass is Terrain)
        {
            ShowMessage("was killed by the environment");
        }
        else if (health < 0 && #CallingClass is Player &&  #CallingMethod is RocketLauncher)
        {
            ShowMessage("was killed with a rocketlauncher by player" + #CallingClass.PlayerName);
        }

    }
}
</code>```

To reduce if-else statements you could have method overrides based on caller methods and classes

答:
You might want to look into Subject-Oriented Programming, as e.g. implemented in the Us Programming Language (by the same people who also did a very nice implementation of Object-Oriented Programming in the Self Programming Language).

In Subject-Oriented Programming, the shape of an object is subjective from the point of view of its caller. I.e. to every caller the object looks different.

This idea was even more generalized in the idea of Context-Oriented Programming in the Korz Programming Language, which has been presented a couple of times this year.

Title: Mutating Programming Language?


答:
You definitively should have a look at the k-d tree. This structure is typically used to answer questions such as "Does this point exist?", "Where is the nearest post office?", or "Who are the employees between 30 and 40 years old, and paid between 2K and 3K?"

So, your problem is a typical range search problem for which this structure is particularly well suited. According to Wikipedia, the worst case time for your problem, with this structure, is O(k.N^(1-(1/k)), where k is the number of dimensions (2, in your case) and N is the number of nodes in the tree.

Some limitations, however:

Building a k-d tree is time consuming, because you have to determine the "median" point in order get a balanced tree. That means that you have to order your points… You can decide to not use the median point as a basis for your splitting planes, but you could get an unbalanced tree, which will be less efficient. As a tradeoff, you can choose the median point among a subset of your point, to avoid a very bad selection.

If you have to add or to remove points, it can be done in log n time. But these operations are likely to unbalance the tree, so your performances will decrease over time, unless you spend extra time for re-balancing it. If you have to frequently add/remove points, and if your dimensions have fixed sizes, you could consider quadtrees as an alternative.

I have never used it, but apparently Java ML has a decent implementation of k-d trees.

Title: Range of values based on key values


问:
Refactoring: reducing duplication without creating flags
I don't know how to refactor a piece of code that differs from other in the number of conditions checked on an if clause. Let me show you a real world example I'm facing right now.

The only difference between the two methods is that on the inner elseif, it checks an additional condition on the new parameter.

Method 1:

public function getKeysToInvalidateOnCreation($entity, $allKeys)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY) {
                    $result[] = $key;
                } elseif (strpos($key, 'id:') === false) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}
```

<p>Method 2:</p>

<pre class="lang-php prettyprint-override"><code>public function getKeysToInvalidateOnModification($entity, $allKeys, $modifiedId)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY) {
                    $result[] = $key;
                } elseif (strpos($key, 'id:') === false ||
                          strpos($key, 'id:'.$modifiedId) !== false) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}
</code>```

What I would do is to extract all the inner code to a new protected method that would have the third parameter as optional, and then do the second check only if that parameter is set. But that has kind of bad smell for me: it seems like adding a flag to the method.

What would be the appropriate refactoring strategy?

答:
PHP isn't a language I have much experience with, but as I understand it both loops are trying to filter the set of keys, so you can extract the structure of the loop into another method that accepts the conditions for filtering as an argument in the form of a function:

private function getKeysWhere($entity, $allKeys, $condition)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY ||
                    $key_type == self::CUSTOM_KEY ||
                    $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}
```

<p>This requires you use PHP 5.3 or above, in order to do things like pass functions as arguments and declare anonymous functions.</p>

<p>This is much more general and powerful than a boolean flag, because instead of picking between two set conditions, you can move the logic for whether to include the key into a separate function and separate the concern of filtering the keys from the concern of what conditions to filter them by.</p>

<p>Now, we define what the conditions for a key to invalidate on modification and on creation are as private helper methods:</p>

<pre class="lang-php prettyprint-override"><code>private function keyIsInvalidOnCreation($key) {
    return strpos($key, 'id:') === false;
}

private function keyIsInvalidOnModification($key, $modifiedId) {
    return strpos($key, 'id:') === false || strpos($key, 'id:'.$modifiedId) !== false;
}
</code>```

And finally, we can define our two methods to get invalid keys in terms of this general method and these two predicates:

public function getKeysToInvalidateOnCreation($entity, $allKeys) {
    return getKeysWhere($entity, $allKeys, 'keyIsInvalidOnCreation');
}

public function getKeysToInvalidateOnModification($entity, $allKeys, $modifiedId) {
    return getKeysWhere($entity, $allKeys, function($key) use ($modifiedId) {
        return keyIsInvalidOnModification($key, $modifiedId)
    });
}
```

The case for modification needs to be wrapped in an anonymous function in order to properly pass in $modifiedId to the predicate and turn it into a function of one argument to work with getKeysWhere. If you're using a library with support for common functional programming tools such as currying and partial application, you can use that here as a cleaner alternative to the anonymous function wrapper. Not sure how possible some of that stuff is in PHP though.

This is fairly heavily decomposed and may be difficult to grok if you're not familiar with functional programming patterns, but it cuts down on the duplication and generalizes well.

Body:
PHP isn't a language I have much experience with, but as I understand it both loops are trying to filter the set of keys, so you can extract the structure of the loop into another method that accepts the conditions for filtering as an argument in the form of a function:

private function getKeysWhere($entity, $allKeys, $condition)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY ||
                    $key_type == self::CUSTOM_KEY ||
                    $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

This requires you use PHP 5.3 or above, in order to do things like pass functions as arguments and declare anonymous functions.

This is much more general and powerful than a boolean flag, because instead of picking between two set conditions, you can move the logic for whether to include the key into a separate function and separate the concern of filtering the keys from the concern of what conditions to filter them by.

Now, we define what the conditions for a key to invalidate on modification and on creation are as private helper methods:

private function keyIsInvalidOnCreation($key) {
    return strpos($key, 'id:') === false;
}

private function keyIsInvalidOnModification($key, $modifiedId) {
    return strpos($key, 'id:') === false || strpos($key, 'id:'.$modifiedId) !== false;
}

And finally, we can define our two methods to get invalid keys in terms of this general method and these two predicates:

public function getKeysToInvalidateOnCreation($entity, $allKeys) {
    return getKeysWhere($entity, $allKeys, 'keyIsInvalidOnCreation');
}

public function getKeysToInvalidateOnModification($entity, $allKeys, $modifiedId) {
    return getKeysWhere($entity, $allKeys, function($key) use ($modifiedId) {
        return keyIsInvalidOnModification($key, $modifiedId)
    });
}

The case for modification needs to be wrapped in an anonymous function in order to properly pass in $modifiedId to the predicate and turn it into a function of one argument to work with getKeysWhere. If you're using a library with support for common functional programming tools such as currying and partial application, you can use that here as a cleaner alternative to the anonymous function wrapper. Not sure how possible some of that stuff is in PHP though.

This is fairly heavily decomposed and may be difficult to grok if you're not familiar with functional programming patterns, but it cuts down on the duplication and generalizes well.


答:
I have had a few scenarios where I'm on holiday and the boss has called to ask me how to do something on a project I've been working on.

In one case I was the build guy, something broke, and I was out at lunch with my girlfriend, and the boss called.  My answer was that I was at lunch and, whatever it was, it could wait until I got back (I didn't actually ask what it was).  Any issue can wait up to an hour.

In another case I was off sick for a week, and my boss (different boss) phoned and asked how to run a tool I was in charge of.  It was obvious, and I told him that, but I told him how to do it anyway since it was 3 minutes of my time.

And another case a few years back, after about 10 minutes of trying to talk things through over the phone with no progress I said it would have to wait until I got back because there's no way I'm spending all my holiday time on the phone with my boss.

My advice is hand over your details, but if a call lasts more than 5 minutes say "look, is this likely to be resolved in the next 5 minutes?  Because if not then I'm working and I want this day back in lieu".  Likewise if they call too often.  Make it clear that it's an emergency number.  To be used in emergencies.

Title: How do you respond to a request for 'emergency contact information' for when you are on vacation?

Body: I want to go on vacation and not think about work at all but they want me to provide them a contact number in the event of an emergency (server goes down, web service malfunctions, etc). I am afraid that it will be abused (they will contact me before trying everything for example) but I also think that if I am on vacation I should not be bothered even if there is an outage. Does anyone have experience with situations like this? What's the tactful approach? Any creative solutions?</p>


答:
So just for other PHP guys that may be struggling with functional programming I want to register here the steps I did following Jack's answer.

First I refactored each method to extract the condition so I could have an identical code base in both (note how the condition was extracted in both):

```<code>public function getKeysToInvalidateOnCreation($entity, $allKeys)
{
    $condition = function($key) {
        return strpos($key, 'id:') === false;
    };
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

public function getKeysToInvalidateOnModification($entity, $modifiedId, $allKeys)
{
    $condition = function($key) use ($modifiedId) {
        return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
    };
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

private function keyIsInvalidOnModification($modifiedId, $key)
{
    return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
}

private function keyIsInvalidOnCreation($key)
{
    return strpos($key, 'id:') === false;
}
</code>```

At these moment, all tests are still green, so I can proceed to extract the common code to a private method:

```<code>public function getKeysToInvalidateOnCreation($entity, $allKeys)
{
    $condition = function($key) {
        return strpos($key, 'id:') === false;
    };
    return $this->getKeysToInvalidate($entity, $allKeys, $condition);
}

public function getKeysToInvalidateOnModification($entity, $modifiedId, $allKeys)
{
    $condition = function($key) use ($modifiedId) {
        return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
    };
    return $this->getKeysToInvalidate($entity, $allKeys, $condition);
}

private function getKeysToInvalidate($entity, $allKeys, callable $condition)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}
</code>```

And everything still green. Thanks Jack

Title: Refactoring: reducing duplication without creating flags

Body:
I don't know how to refactor a piece of code that differs from other in the number of conditions checked on an if clause. Let me show you a real world example I'm facing right now.

The only difference between the two methods is that on the inner elseif, it checks an additional condition on the new parameter.

Method 1:

public function getKeysToInvalidateOnCreation($entity, $allKeys)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY) {
                    $result[] = $key;
                } elseif (strpos($key, 'id:') === false) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}
```

<p>Method 2:</p>

<pre class="lang-php prettyprint-override"><code>public function getKeysToInvalidateOnModification($entity, $allKeys, $modifiedId)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY) {
                    $result[] = $key;
                } elseif (strpos($key, 'id:') === false ||
                          strpos($key, 'id:'.$modifiedId) !== false) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}
</code>```

What I would do is to extract all the inner code to a new protected method that would have the third parameter as optional, and then do the second check only if that parameter is set. But that has kind of bad smell for me: it seems like adding a flag to the method.

What would be the appropriate refactoring strategy?

Body:
So just for other PHP guys that may be struggling with functional programming I want to register here the steps I did following Jack's answer.

First I refactored each method to extract the condition so I could have an identical code base in both (note how the condition was extracted in both):

public function getKeysToInvalidateOnCreation($entity, $allKeys)
{
    $condition = function($key) {
        return strpos($key, 'id:') === false;
    };
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

public function getKeysToInvalidateOnModification($entity, $modifiedId, $allKeys)
{
    $condition = function($key) use ($modifiedId) {
        return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
    };
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

private function keyIsInvalidOnModification($modifiedId, $key)
{
    return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
}

private function keyIsInvalidOnCreation($key)
{
    return strpos($key, 'id:') === false;
}

At these moment, all tests are still green, so I can proceed to extract the common code to a private method:

public function getKeysToInvalidateOnCreation($entity, $allKeys)
{
    $condition = function($key) {
        return strpos($key, 'id:') === false;
    };
    return $this->getKeysToInvalidate($entity, $allKeys, $condition);
}

public function getKeysToInvalidateOnModification($entity, $modifiedId, $allKeys)
{
    $condition = function($key) use ($modifiedId) {
        return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
    };
    return $this->getKeysToInvalidate($entity, $allKeys, $condition);
}

private function getKeysToInvalidate($entity, $allKeys, callable $condition)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

And everything still green. Thanks Jack


问:
Declaring lambdas in Java8
What would be the best practice to declare lambdas in Java8 code? How it was designed to be used?

For example, let's say that we have a method that accept a Function. I want to provide function implementation that can be reusable. So I can do this:

[A] Implement a Function interface:

```<code>public class Foo implements Function<A,B> {
    public B apply(A a) {...}
}
...
useFunction(new Foo());
</code>```

[B] Declare Function as lambda in some static field:

```<code>public interface Foo {
    Function<A,B> bar = it -> { ....}
}
...
useFunction(Foo.bar);
</code>```

[C] Use method reference:

```<code>public class Foo {
    public static B bar(A a) {...}
}
...
useFunction(Foo::bar);
</code>```

Until functional programing in java8, I tried not to pollute code with statics. However, now I am somehow 'forced' to use statics (or global singletons) for storing reusable lambdas.

EDIT

I have code that returns the following on several places:

```<code>return CompletableFuture.supplyAsync(() -> {
...
}
.exceptionally(FooExceptionWrapper::wrap);
</code>```

As you see, I want to share the wrapper (that is a Function) instances, and yet to remain fluent with the code. There are many ways how we can share this.

If I create new instance every time (like in A) then we are going to create new instance on every call, which is fine; yet GC is going to be called more frequently. I can instead create a singleton and since this is a Function, sharing it across the threads is not going to be a problem. So I might store it in some variable. Now, I would like to put the handling code out of this class (simple to reduce the size and the responsibility of the class). So I use approach A - but still want to see if there is more 'proper' way for this. There are not many java8 projects out there, and lot of people simple use static fields (like in B); Im just questioning all that.

答:
There are actually many more ways to do this in Java 8.

To start, if what you want to do in function is simple enough (e.g. a one liner), than probably a simple lambda is the way to go.

```<code>foo( it -> it.getValue() > 10 ? "A" : "B" )
</code>```

In this approach you probably won't have to worry for how many instances of the lambda target object are created, the JLS makes concessions so that the same instance can be be reused (unless it is a capturing lambda)

Now, if the code is a bit more complex, than you may consider using method references. There are many types of method references, not just the static method reference that you mention in your example.

You may want to read State of Lambda to make that clearer.

Certainly the definition of a static field in an interface to contain the lambda target object sounds like a pretty bad idea to me too. Static fields in interfaces are typically used for constants since they are by default static and final, and therefore I have difficulty conceiving a good scenario for this.

Title: Declaring lambdas in Java8

Body:
There are actually many more ways to do this in Java 8.

To start, if what you want to do in function is simple enough (e.g. a one liner), than probably a simple lambda is the way to go.

foo( it -> it.getValue() > 10 ? "A" : "B" )

In this approach you probably won't have to worry for how many instances of the lambda target object are created, the JLS makes concessions so that the same instance can be be reused (unless it is a capturing lambda)

Now, if the code is a bit more complex, than you may consider using method references. There are many types of method references, not just the static method reference that you mention in your example.

You may want to read State of Lambda to make that clearer.

Certainly the definition of a static field in an interface to contain the lambda target object sounds like a pretty bad idea to me too. Static fields in interfaces are typically used for constants since they are by default static and final, and therefore I have difficulty conceiving a good scenario for this.


答:
In C++ you can inherit from types that doesn't share common ancestor and avoid the "dreaded diamond" problem altogether. In fact this is what most of C++ code do: design around the problem. When there is no other option, then one can choose between virtual inheritance or non-virtual one. Each has its own advantages and disadvantages, but none is a truly "successfully addressed" solution.

In Java, every class inherits Object implicitly. Now this means that every multiple inheritance will create the "dreaded diamond" right away! Which means that even simple hierarchy would obligatory turn into a nightmare. This is where interface concept comes to the rescue. In C++ interface is just another class. In Java, interface is unique by not inheriting from Object. Java solves the "dreaded diamond" problem in same way that 99% of C++ code does it: by not letting diamonds to happen in the first place.

Bottom line: introducing diamond inheritance to Java would help in very few cases at a huge cost of allowing very difficult to understand code.

You must keep in mind that the biggest advantage that Java holds over C++ is that it doesn't let programmers to play with dangerous features that are mostly unnecessary (in jargon "shooting oneself in the foot"). Don't ask "why we don't have X", ask yourself "which types of problems cannot be solved without X". Most of the time you'd get a simple answer: "none". Or "none that matter to overwhelming majority of Java users".


问:
Including GPLv2 code in GPLv3 code
I would like to use some code that was released under GPLv2 in my project.

I released my project with the GPLv3 license. Can I do this, or do I have to downgrade to GPLv2?

答:
In your case, the particular software you are using is licensed under "GPLv2 or any later version," which can be included in GPLv3-licensed code. If the code you wanted to use were using GPLv2 only, then it would not be legally possible to include that code in your GPLv3-licensed distribution.

We can consult the inter-GPL-compatibility table from the FSF's GPL FAQ to see the two cases:

The top marked space disallows a GPLv3 project from including GPLv2-only code. In that case, you must either license your code as GPLv2, or the author of the GPLv2-only code must re-license as GPLv2-or-later.

The space immediately below that, however, allows a GPLv3 project to include code that is licensed under "GPLv2 or any later version". (This is because you may treat the GPLv2-or-later code as GPLv3 code, and then there's no problem at all.)

If you have some GPLv2-only code that you want to include in your GPLv3 project, you might look at the space to the left of the circled "NO" and think, "Wait! I can license my project as GPLv2-or-later and still include the GPLv2-only code! Then, I'll freely upgrade my project to GPLv3 -- problem solved." However, that space has a footnote:

[2] While you may release your project (either your original work and/or work that you received and modified) under GPLv2-or-later in this case, note that the other code you're using must remain under GPLv2 only. As long as your project depends on that code, you won't be able to upgrade the license of your project to GPLv3-or-later, and the work as a whole (any combination of both your project and the other code) can only be conveyed under the terms of GPLv2.

Thus, a project that includes GPLv2-only code may be licensed under GPLv2-or-later, but it can't actually upgrade as a whole to GPLv3, because it's held back by the GPLv2-only code. However, any parts of your GPLv2-or-later project that are not GPLv2-only may be freely upgraded when separated from the GPLv2-only code.

Title: Including GPLv2 code in GPLv3 code


问:
When should I use event-based programming?
I have been passing callbacks or just triggering the functions from other function in my programs to make things happen once tasks complete. When something finishes, I trigger the function directly:

var ground = 'clean';

function shovelSnow(){
    console.log("Cleaning Snow");
    ground = 'clean';
}

function makeItSnow(){
    console.log("It's snowing");
    ground = 'snowy';
    shovelSnow();
}
```

<p>But I've read about many different strategies in programming, and one that I understand to be powerful, but have not yet practiced, is event-based (I think a method I read about was called <em>"pub-sub"</em>):</p>

<pre class="lang-js prettyprint-override"><code>var ground = 'clean';

function shovelSnow(){
    console.log("Cleaning Snow");
    ground = 'clean';
}

function makeItSnow(){
    console.log("It's snowing");
    ground = 'snowy';
    $(document).trigger('snow');
}

$(document).bind('snow', shovelSnow);
</code>```

I'd like to understand the objective strengths and weaknesses of event-based programming, vs just calling all of your functions from within other functions. In which programming situations does event-based programming make sense to use?

答:
Event-based programming is used when the program does not control the sequence of events that it performs. Instead, program flow is directed by an outside process such as a user (e.g. GUI), another system (e.g. client/server), or another process (e.g. RPC).

For example, a batch processing script knows what it needs to do so it just does it. It is not event-based.

A word processor sits there and waits for the user to start typing. Keypresses are events that trigger functionality to update the internal document buffer. The program cannot know what you want to type, so it must be event-driven.

Most GUI programs are event-driven because they are built around user interaction. However, event-based programs are not limited to GUIs, that is simply the most familiar example to most people. Web servers wait for clients to connect and follow a similar idiom. Background processes on your computer may respond to events too. For example, an on-demand virus scanner may receive an event from the OS regarding a newly created or updated file, then scan that file for viruses.


问:
Progressive Enhancement vs. Single Page Apps
I just got back from a conference in Boston called An Event Apart.

A really popular theme amongst the speakers was the idea of progressive enhancement - a site's content should go in the HTML, and JavaScript should only be used to enhance behavior.

The arguments that the speakers gave for progressive enhancement were very compelling. Not only is it a solid pattern for supporting older browsers, and devices on a network with low bandwidth, but HTML fails much more gracefully than JavaScript (i.e. markup that is not supported is just ignored, while if a browser throws an exception while executing your script - you are hosed).

Jeremy Keith gave a particularly insightful talk about this.

But what about single page web apps like Backbone and Angular? The whole design behind these frameworks seems to push the developer toward moving content out of the HTML, and into something like a JSON API.

I can not seem to gel these two design patterns: progressive enhancement vs. single page web apps. Are there instances when one is better than the other? Or are they not even antagonistic technologies, and I am missing something here with my mental model?

答:
Progressive enhancement and a Single Page App can co-exist. The two most compelling arguments I've heard for building apps in this way are:

Fault tolerance in situations where the HTML file downloads in full but referenced scripts fail to download completely thanks to network connectivity that drops in and out (possible on mobile networks)

Potential for improved perceived performance on initial page load (by reducing Start Render times)

Server-side rendering (this is for users, not just SEO reasons) and cutting-the-mustard are two techniques that can help build progressively enhanced Single Page Apps with modern client-side JS frameworks.

Some client-side JS frameworks are easier to get working with server-side rendering than others (beware some server-side rendering solutions and framework combinations do not produce working SPAs as the server-rendered page is only intended for search engine consumption, not end-users).

At time of writing, React.js and Ember (with the upcoming FastBoot) are the two I'm aware of that have or are trying to make server-side rendering a first class citizen; the server-side rendered page is still a working SPA when it's parsed on the client browser.


问:
Metric by which to hold developers accountable
I asked a question on lines of code per hour and got torn a new one.  So my matured follow-up question is this:

If not lines of code, then what is a good metric by which to measure (by the hour/day/unit-of-time) the effectiveness of remote programmers?

答:
Metrics work best in factories, and programmers don't work on an assembly line.

I completely understand the desire to measure productivity.

But would you use the same metric for a family doctor and a heart surgeon? How about for Michelangelo painting the Sistine Chapel, and some guy in Mexico cranking out black velvet Elvis paintings?

Louis de Broglie wrote a doctoral thesis that was so short, the examiners were going to reject it - except de Broglie was a highly-placed aristocrat, and they needed a good excuse. So the examiners sent it to Einstein, who not only didn't reject it, he referred it to the Nobel committee, and de Broglie got the Nobel Prize in Physics for it five years later.

Numerical measures work best on work that's repetitive, like casting iron or screwing bolts on car doors. But if you're repeating code that's been done before, you don't need a programmer, you just need a copy-and-paste. Programming is fundamentally a creative discipline, and productivity depends entirely on what you're doing.

Some days, I crank out 1000 lines of code. Today, I'm going to be fixing coordinate geometry bugs, and the code might shrink. If I had to fix a bug in a Linux kernel driver, I might spend all day on debugging, and not write a line of new code.

Measuring programmer productivity is very, very, very subjective.

If you want to know if Joe is productive, find Sally and Ralph, who know what Joe's doing and are proficient in the same areas, and ask them.

The best numerical system I've ever seen has been Agile's planning poker points. That's just a fancy way of asking Joe and Sally and Ralph how hard they think Joe's upcoming job is likely to be. Then you can measure points-per-week productivity for each team member. But even then, it takes a while to calibrate a team's estimations, and the numbers are fuzzy and easily thrown off.

Many people want productivity estimates so they can do schedule planning. It's kind of the "plug it into MS Project, look at the critical path, and there's your ship date" theory. I have never, ever seen that work - there are just too many unknowns. If you want that, use Waterfall, design everything up front, don't permit any change orders, and be prepared to be disappointed anyway.


问:
Asp.net Web Api Controller design
I am developing services using Asp.Net Web Api. I am debating on design of our controllers.
We have this common scenario where user will be presented with bunch of search field, once he enters the search criteria we will show summary of records (not the complete details), user will select one summary record and can go to details for this.

Ex.

```<code>class PersonSummary {
   string FirstName {get;set;}
   string LastName {get;set;}
   string Gender {get;set;}
}

class Person {
   string FirstName {get;set;}
   string LastName {get;set;}
   string Gender {get;set;}
   string SSN {get;set;}
   string Race {get;set;}
   Address Address {get;set;}
}
</code>```

User will search by user first\last name and we will show will list of PersonSummary records, he can select one PersonSummary to look at the details (Person record).

Now is it best design that we go with two controllers PersonSummaryController and PersonController?

Thank you.

答: I don't see a need for two controllers. You're dealing with one type of resource (Person), but asking for data in two formats (summary and detail). I would leave it at one controller and go on with life. </p>

Title: Asp.net Web Api Controller design


问:
Generating URL's that fill forms on my site
I have a asp.net web forms page where admins can search by user last name and then select them and approve or deny their access to the site. When users request access, an email is sent out informing admins. I want to be able to send a link that populates the page with that users info for easier approval. How would I approach this?</p>

答:
Since the user has to enter his data into a form, simply save that to the database. A common way to do this could be to have a user table with a user ID, and a flag or status code stating that the record is inactive and needs administrator attention.

From here, the web app should send a link to the administrator with the user ID embedded in the URL. It would look something like this:

```<code>http://www.example.com/ActivateUser.asp?id=1234
</code>```

When the admin user clicks on the link, the server responds with a page with that user's information pre-filled in the form ready for the admin to edit in his browser.

The admin could then press a button to active the user, edit that flag or status code, whatever the implementation details are.

This is a very common task and you can view the source code for one of any number of open-source message boards or CMS packages for examples. They are typically written in PHP as opposed to ASP and much more complex, but the general idea is the same.

Body:
Since the user has to enter his data into a form, simply save that to the database. A common way to do this could be to have a user table with a user ID, and a flag or status code stating that the record is inactive and needs administrator attention.

From here, the web app should send a link to the administrator with the user ID embedded in the URL. It would look something like this:

http://www.example.com/ActivateUser.asp?id=1234

When the admin user clicks on the link, the server responds with a page with that user's information pre-filled in the form ready for the admin to edit in his browser.

The admin could then press a button to active the user, edit that flag or status code, whatever the implementation details are.

This is a very common task and you can view the source code for one of any number of open-source message boards or CMS packages for examples. They are typically written in PHP as opposed to ASP and much more complex, but the general idea is the same.


问:
Using macros to implement a generic vector (dynamic array) in C. Is this a good idea?
So far I have only done personal projects at home. I hope to get involved in some open source project some time next year. The languages I that have been using the most are C and C++. I have used both languages for over a year and I feel like I have become quite proficient with both of them, but I really don't know which one I like better.

I personally like C because I think it is simple and elegant. To me C++ seems bloated many unnecessary features that just complicates the design process. Another reason to why I like to use plain C is because it seems to be more popular in the free and open-source software world.

The feature that I miss the most from C++ when I use plain C is probably the std::vector from STL (Standard Template Library).

I still haven't figured out how I should represent growing arrays in C. Up to this point I duplicated my memory allocation code all over the place in my projects. I do not like code duplication and I know that it is bad practice so this does not seems like a very good solution to me.

I thought about this problem yesterday and came up with the idea to implement a generic vector using preprocessor macros.

It looks like this:

```<code>int main()
{
    VECTOR_OF(int) int_vec;
    VECTOR_OF(double) dbl_vec;
    int i;

    VECTOR_INIT(int_vec);
    VECTOR_INIT(dbl_vec);

    for (i = 0; i < 100000000; ++i) {
        VECTOR_PUSH_BACK(int_vec, i);
        VECTOR_PUSH_BACK(dbl_vec, i);
    }

    for (i = 0; i < 100; ++i) {
        printf("int_vec[%d] = %d\n", i, VECTOR_AT(int_vec, i));
        printf("dbl_vec[%d] = %f\n", i, VECTOR_AT(dbl_vec, i));
    }

    VECTOR_FREE(int_vec);
    VECTOR_FREE(dbl_vec);

    return 0;
}
</code>```

It uses the same allocation rules as std::vector (the size starts as 1 and then doubles each time that is required).

To my surprise I found out that this code runs more than twice as fast as the same code written using std::vector and generates a smaller executable! (compiled with GCC and G++ using -O3 in both cases).

My question is:

Would you recommend using this in a serious project?

If not then I would like you to explain why and what a better alternative would be.

答:
My question is: Would you recommend using this in a serious project?

Yes! Here is something that is mostly true about library functions: they necessarily have to be generally applicable in order to accommodate many users with different requirements.  If you know the underlying algorithm, the library function is going to be larger and slower than your own implementation.  Most of the time we don't care, because size and speed aren't an issue.  However once speed does become an issue and the bottleneck is the library function (very often with library sorting algorithms), simply understanding the algorithm and writing something that works for you can result in dramatic speed improvements.  I understand you discovered this in another way (reproducing a feature from std::vector in C) and aren't asking an optimization question.  But it's worth mentioning that what you've learned will come in very handy in the future when working in Java, C++, etc. and you run into a speed bottleneck that crushes your project.  This can happen often in computationally-intensive projects.


答:
In an Event-based application the concept of Event Listeners will give you the ability to write even more Loosely Coupled applications.

For example a third-party module or plug-in can delete a record from the database and then trigger the receordDeleted event and leave the rest to the event listeners to do their job. Everything will work fine, even though the triggering module doesn't even know who's listening for this particular event or what should happen next.

Title: When should I use event-based programming?

Body:
I have been passing callbacks or just triggering the functions from other function in my programs to make things happen once tasks complete. When something finishes, I trigger the function directly:

var ground = 'clean';

function shovelSnow(){
    console.log("Cleaning Snow");
    ground = 'clean';
}

function makeItSnow(){
    console.log("It's snowing");
    ground = 'snowy';
    shovelSnow();
}
```

<p>But I've read about many different strategies in programming, and one that I understand to be powerful, but have not yet practiced, is event-based (I think a method I read about was called <em>"pub-sub"</em>):</p>

<pre class="lang-js prettyprint-override"><code>var ground = 'clean';

function shovelSnow(){
    console.log("Cleaning Snow");
    ground = 'clean';
}

function makeItSnow(){
    console.log("It's snowing");
    ground = 'snowy';
    $(document).trigger('snow');
}

$(document).bind('snow', shovelSnow);
</code>```

I'd like to understand the objective strengths and weaknesses of event-based programming, vs just calling all of your functions from within other functions. In which programming situations does event-based programming make sense to use?


问:
Scrum - how to carry over a partially complete User Story to the next Sprint without skewing the backlog
We're using Scrum and occasionally find that we can't quite finish a User Story in the sprint in which it was planned. In true Scrum style, we ship the software anyway and consider including the User Story in the next sprint during the next Sprint Planning session. Given that the User Story we are carrying over is partially complete, how do we estimate for it correctly in the next Sprint Planning session? We have considered:

a) Adjusting the number of Story Points down to reflect just the work which remains to complete the User Story. Unfortunately this will mess up reporting the Product Backlog.

b) Close the partially-completed User Story and raise a new one to implement the remainder of that feature, which will have fewer Story Points. This will affect our ability to retrospectively see what we didn't complete in that sprint and seems a bit time consuming.

c) Not bother with either a or b and continue to guess during Sprint Planning saying things like "Well that User Story may be X story points, but I know it's 95% finished so I'm sure we can fit it in."

答:
We track the time spent in the sprint iteration for capitalization purposes, (hours burnt on tasks related to a user story), and move the pointed user story along if the goal of the PO is to keep trucking on it during the next sprint, leaving points the same.

If the PO's goal is to move something else up in its place, then we'd simply put the unfinished story into the backlog and do whatever they wanted.  Leaving the original estimate of points is my recommendation, because if you had a habit of biting off more than you could chew, every sprint, you'd be "completing" story points in a sprint that weren't fully-done and clean-tested items.

If you did want to leave something in the sprint, pointed, or you had to ship, I'd think you'd determine a slice point within the original story, to which you did reach the done-point, and commit that smaller piece for your iteration.  Then the remainder could be re-pointed, and dropped into the backlog.  That would be an opportunity to re-estimate because you agreed with your team to break the story into slices.


问:
To what extent can impact analysis of a code change be automated?
I'm not sure how possible it even is but as a programmer I have a sense of risk involved when I'm making changes to a code base.

I've never seen a tool which basically tells me, as I'm coding, how far reaching my changes potentially are.

Examples off the top of my head (which are probably debatable but this is just to be less abstract):

Adding a property to a POCO is a "green" change

Making a field readonly is a "green" change

Adding a constructor when Unity DI is present is a "yellow" change

Modifying conditional logic in a public method which has usages that span multiple assemblies is a "red" change

Is it possible? If yes, to which extent?

(Note this question is not a request for a specific tool.)

答:
Does anything like this exist, or is it even possible?

Sure, there are tools that try to determine impact of a change across your codebase.

No, they aren't foolproof. They're not foolproof because languages invariably allow things to escape their control. Things like reflection, working with files/databases, concurrency... all of these are things that cannot be dealt with via static analysis. If they could be (quickly) then the compiler would do it or we'd use these tools more frequently. Some languages allow more/more useful checks at the expense of flexibility. On the other side is dynamic languages where this sort of thing would be highly impractical.

In practice, this is what unit tests do. They provide a quick, reusable set of regression checks to let you know clearly that your change has impacted stuff (or not). People have even attempted to automatically generate those, but that only tends to get the edge case sort of checks, not the meaty "does this work?" checks that humans know.


问:
How can I develop a productive Git(hub) branch workflow for an open source project?
I am writing a simple framework that I want to open source just for experience (and fun!). However, it has some cool ideas that could make it grow to a larger project and I want to be ready if that ever happens. I highly doubt that that will happen, but I want to use this as a learning experience on how to properly run an open source project.

I want to dive right into the development. I'm not too worried about the actual code since it should be mostly simple. However, I'm not that experienced with Github. I mean, I know all the basics and such, but I don't really know how to use all of the tools to my advantage.

How should I manage a workflow to best accommodate developers? I'm going to try to encourage the "standard" procedure:

Fork the repository

Clone the repository to your Git client

Make a new branch for the work

Do the actual work

Commit your work (if multiple commits, rebase them to create one commit for easy history on the main repo)

Submit a pull request with that one commit

Then, obviously, I will choose if I want to pull it or not. Here's where I get stuck. How should I manage my branches?

I drafted up this design:

Proposed Workflow:

Basically:

The master branch is for stable releases. Individual pull requests are only sent to the master branch if it's a critical bug and needs an individual release ASAP.

The beta branch is for the code for the next stable release. Bug fixes will be pulled to this branch.

The alpha branch is where the feature requests are added.

When a commit (not a pull request) is added to either the master or beta branch, the changes are "cascading" (i.e. a pull request is automatically created so that a commit to master will also be on beta and alpha; a commit on beta will be on alpha). I would do this with a simple script. Albeit it'd be somewhat ghetto, but it'd be automatic.

For a standard release, the beta would be merged into the master and then the alpha into the beta branch.

The reason for this is the feature requests aren't put into the next version so they're stable enough to be in the stable release.

Is this dumb? A consolidated "dev" branch would be the easiest to manage, but I'm afraid that some bugs would still get through. I guess I'd have to stop accepting feature additions a little bit before I release a new version.

EDIT: This question is extremely similar to my question: Is there an established or defined best practice for source control branching between development and production builds?. However, I'm looking at my proposed method vs. just not handling pull requests before a new release. Also, this is about open source software (so it might be harder to train new people on the system for this project).

答:
There are many different approaches, and it depends both on your application and on your team's personality. Here is a good summary of a few branching workflows in Git:

http://sethrobertson.github.io/GitBestPractices/#workflow

The link there labelled "Git-flow branching model" is a very popular approach.

However, there are some who think that all the process there is too cumbersome to really innovate. Read the last link under "Branch Workflows": "Who needs process".

That's why I say it depends on your specific application and also on your personality/preferences.


问:
Is there still a need for writing SQL?
With so many ORM tools for most modern languages, is there still a use case for writing and executing SQL in a program, in a language/environment that supports them?  If so why?

For clarity: I'm not asking about if programmers need to know SQL, or if I should have a SQL tool on my desktop.  I'm asking specifically why I might have it in code (or config, or whatever) as opposed to an ORM.

答:
You're more comfortable writing SQL to query data than you are writing procedural code.

Your ORM, while beautiful to look at, generates horrifically slow SQL in some critical area.

You need to take advantage of functionality exposed by your RDBMS that is not / cannot be made available through your ORM.

Every time you type SELECT * FROM..., God kills a kitten. And you hate kittens.

You aren't using an ORM, OOP, or a modern language.

Title: Is there still a need for writing SQL?


答:
An event is a notification describing an occurrence from the recent past.

A typical implementation of a event-driven system utilises an event dispatcher and handler functions (or subscribers). The dispatcher provides an API to wire handlers up to events (jQuery's bind), and a method to publish an event to its subscribers (trigger in jQuery). When you're talking about IO or UI events, there's also usually an event loop, which detects new events such as mouse-clicks and passes them to the dispatcher. In JS-land, the dispatcher and event loop are provided by the browser.

For code that interacts directly with the user - responding to keypresses and clicks - event-driven programming (or a variation thereof, such as functional reactive programming) is almost unavoidable. You, the programmer, have no idea when or where the user is going to click, so it's down to the GUI framework or browser to detect the user's action in its event loop and notify your code. This type of infrastructure is also used in networking applications (cf NodeJS).

Your example, wherein you raise an event in your code rather than calling a function directly has some more interesting tradeoffs, which I will discuss below. The main difference is that the publisher of an event (makeItSnow) does not specify the receiver of the call; that's wired up elsewhere (in the call to bind in your example). This is called fire-and-forget: makeItSnow announces to the world that it's snowing, but it doesn't care who's listening, what happens next, or when it happens - it simply broadcasts the message and dusts off its hands.

So the event-driven approach decouples the sender of the message from the receiver. One advantage this affords you is that a given event may have multiple handlers. You could bind a gritRoads function to your snow event without affecting the existing shovelSnow handler. You have flexibility in the way your application is wired up; to turn off a behaviour you just need to remove the bind call rather than go hunting through the code to find all the instances of the behaviour.

Another advantage of event-driven programming is that it gives you somewhere to put cross-cutting concerns. The event dispatcher plays the role of Mediator, and some libraries (such as Brighter) utilise a pipeline so that you can easily plug-in generic requirements such as logging or quality-of-service.

Full disclosure: Brighter is developed at Huddle, where I work.

A third advantage of decoupling the sender of an event from the receiver is that it gives you flexibility in when you handle the event. You could process each type of event on its own thread (if your event dispatcher supports it), or you can put raised events onto a message broker such as RabbitMQ and handle them with an asynchronous process or even process them in bulk overnight. The receiver of the event could be in a separate process or on a separate machine. You don't have to change the code which raises the event to do this! This is the Big Idea behind "microservice" architectures: autonomous services communicate using events, with messaging middleware as the backbone of the application.

For a rather different example of event-driven style, look to domain-driven design, where domain events are used to help keep aggregates separate. For example, consider an online store which recommends products based on your purchase history. A Customer needs to have its purchase history updated when a ShoppingCart is paid for. The ShoppingCart aggregate might notify the Customer by raising a CheckoutCompleted event; the Customer would get updated in a separate transaction in response to the event.

The main downside of this event-driven model is indirection. It's now harder to find the code which handles the event because you can't just navigate to it using your IDE; you have to figure out where the event is bound in the configuration and hope that you've found all the handlers. There's more stuff to keep in your head at any one time. Code style conventions can help here (for example, putting all the calls to bind in one file). For the sake of your sanity, it's important to only use one event dispatcher and to use it consistently.

Another disadvantage is that it's difficult to refactor events. If you need to change the format of an event you also need to change all the receivers. This is exacerbated when the subscribers of an event are on different machines, because now you need to synchronise software releases!

In certain circumstances, performance may be a concern. When processing a message, the dispatcher has to:

Look up the correct handlers in some data structure.

Build a message processing pipeline for each handler. This may involve a bunch of memory allocations.

Dynamically call the handlers (possibly using reflection if the language requires it).

This is certainly slower than a regular function call, which only involves pushing a new frame on the stack. However, the flexibility that an event-driven architecture affords you makes it much easier to isolate and optimise slow code. Having the ability to submit work to an asynchronous processor is a big win here, as it allows you to serve a request immediately while the hard work is dealt with in the background. In any case, if you're interacting with the DB or drawing stuff on the screen then the costs of IO will totally swamp the costs of processing a message. It's a case of avoiding premature optimisation.

In summary, events are a great way to build loosely coupled software, but they are not without cost. It would be a mistake, for example, to replace every function call in your application with an event. Use events to make meaningful architectural divisions.


问:
Is there an algorithm to determine the amount of work needed to keep workers busy?
I wrote a multi-threaded program that randomly generates strings, and after generating, checks to see if the string contains a certain value. Namely, StringGenerator and StringChecker. What I'm trying to figure out is how many StringGenerator threads I would need in order to keep StringChecker busy.

All StringGenerator threads have a reference to a Queue that contains all of the Strings needed to be checked, and when they generate a String, it gets added to the Queue. All StringChecker threads also have a reference to the same Queue and poll it to get the next string, and checks to see if it contains the keyword.

Because generating the Strings takes more time than checking them, what I want to know is if there are any equations, algorithms or analyses that can be done on the code that can help tell me approximately how many threads of each I will need such that the sum of all Strings generated by the StringGenerators is as close to the number of strings checked by the StringCheckers as possible.

答: Assuming that the time it takes to generate and check strings is fairly regular, you can hard code a ratio after doing some timing. Suppose generating a string takes on average N nanoseconds, and checking it takes M nanoseconds. If it takes three times as long to generate as it does to check, that is if N / M = 3, then there should be three times as many generators as there are checkers - three generators for each checker. So do some profiling, find some averages, and figure out what ratio you need.</p>


问:
Data structure well suited for duplicate entries
I'm in the process of getting to know (modern) filesystems. As part of it, I came across log structured filesystems that also handle allocations in a log structured way. I wonder how they handle allocation of space in the most efficient way and if they probably use a data structure, I'm not aware of.

As far as I understood, an allocation related log entry, stored on the disk, basically consists of:

```<code>+------------------------+
| offset | length | type |
+------------------------+
</code>```

Where offset is the offset on disk (or within a region of it), length as the amount of blocks (or bytes) and type as either allocation operation or free operation.

Once read from disk, these entries are managed and merged within a specific (tree-like) data structure using just one type, i.e. merge all allocations the be able to tell about offsets that start a free space area up to length length.

It's easy to sort this structure by offset, since this value is unique. But for allocation operations, it'd be easier to have a separate structure where the data is managed by length, i.e. I want to allocate x blocks, search for x and if the result is less than x, give me the next entry that is larger than x and use it's offset for an allocation operation of the type alloc(offset, x).

Naturally, such a data structure would need to handle duplicates, since the same length (of free blocks) can be available at multiple offsets.

So which data structure would be the best for this job? As far as I know, rb-tree, AVL tree or b-tree (and it's variants) do require unique keys?!

Add-On question: How's the allocation strategy of filesystems that use a log based structure? Did I misunderstood the log-entry on disk?

An approach I could think of, would be using an rb-tree similar to the one provided by the Linux kernel and extend the rb-tree node (with length as key) by an array/linked list of offsets with the same length. But both, array and linked list, seem to be suboptimal approaches to the problem.

答:
There's good information to be found on this topic in the paper on the implementation of Venti (Plan 9's deduplicating filesystem) and its data structure approach.

In addition, Marco Peereboom has some implementation resources on his work on Epitome (which was heavily inspired by Venti). You can see some slides or a paper from which the slides were based that was presented at AsiaBSDCon in 2010. These slides also include a discussion around network transport for such a filesystem. In addition, source can be found through the wiki page, though it doesn't seem that there's been any public work on this project in some years.

Finally, if you're up for some serious reading, see this Masters thesis work: "Online De-duplication in a Log-Structured File System for Primary Storage" by Stephanie Jones of UCSC. It provides at a minimum a decent study of the algorithms and data structures used in such storage systems, as well as some performance metrics in common real-world workloads. If nothing else for you, it has a wealth of references to other papers on the topic.