How can we dope out what the programmer want to do? And how can we get the programmer's purpose? How to get the different between below: 1. arr.slice(1, 100).slice(2, 10); 2. temp = arr.slice(1, 100);doSome(temp);temp.slice(2, 10);I consider that the work of this aspect could be done by the java compiler,do u think?
to Wangwenyou: I don't quite understand your approach. If it only does "连续出现两次相同的状态" Can it work with arr.rotate(2).reverse().rotate(2)?To cocia(高亚): what do you mean by "what the programmer want"? Actually whatever we do, it should not affect the observable behavior of the array. i.e. the solution should provide the same functionality as the simple decorator approach. The only difference is performance and memory usage.
hint: the methods don't have to be mutable. i.e. if arr is [1, 2, 3] after calling arr2 = arr.reverse() arr2 is [3, 2, 1], arr can still be [1, 2, 3]
i.c. My mean is that we cann't get the nead info from the java expression: arr.slice(1, 100).rotate(2).slice(2, 10).rotate(2); Will u keep the status after calling each mothed?
For reverse/ReverseArray, this is easy. You just return a straight array in the reverse method of the ReverseArray, since the reverse of a reverse is straight. This will eliminate the overhead of get/set method, but cannot avoid generating a lot of garbage objects. For the rest, I'm not sure, it depends on whether two successive operations can be simplified into one. If yes, then it's easy like the ReverseArray. Otherwise we'll need some serious consideration, since introducing new Arrays that embed two successive operations is a lot of work, and their reverse/slice/etc methods will need to be optimized too. Anyway, the general idea is that the reverse/slice/etc methods of the ReverseArray/SliceArray/etc classes represent two successive operations, and you should optimize accordingly.
More hints:I would say wangwenyou's sense is so keen. It is also State pattern in my mind. My solution may not be the best one. Basically, we should get some observations of the interactions between each two operations. i.e. 1. arr.rotate(i).reverse() == arr.reverse().rotate(-i) 2. arr.rotate(i).rotate(j) == arr.rotate(i+j) 3. arr.reverse().reverse() == arr 4. arr.rotate(i).slice(j, k) == arr.slice(i+j, k) if the slice does not overlap with the roll-over part; no simplification otherwise5. arr.slice(i, j).slice(k, l) == arr.slice(i+k, l) if l <= j, exception otherwise 6. arr.concat(arr2).slice(i, j) == arr.slice(i, j) if i<arr.length && i+j<arr.length; arr2.slice(i-arr.length, j) if i>arr.length; no simplification otherwise ......
to abcabcabc: when I say arr2=arr.reverse(); and arr is [1, 2, 3], arr2 is [3, 2, 1] it does not have to be an array copy operation.the [1, 2, 3] or [3, 2, 1] is only determined by your Array implementation.In other words, arr only appears as [1, 2, 3] when you call arr.get(0), arr.get(1), arr.get(2) respectively, arr2 only appears as [3, 2,1] when you call arr2.get(0), arr2.get(1), arr2.get(2) respectively.
to jimjxr: "Anyway, the general idea is that the reverse/slice/etc methods of the ReverseArray/SliceArray/etc classes represent two successive operations, and you should optimize accordingly." don't quite follow you. do you mean you need classes like RevRotateArray, RotateRevArray, RevSliceArray etc? even that, how do you optimize revRotate + RotateRev?
这道题真麻烦：） 如果JDK或JGL的设计也能智能化到这程度就好了。 佩服！
If you can't express reverse+rotate in another single operation, then a class like RevRotateArray MAY have its place, but I'm not sure if this is a good idea, please see 2nd paragraph in my post. As I said, if two operations can be simplified into one, like reverse+reverse=identity, then it's trivial, something like ReverseArray.reverse() = IdentityArray can solve it. If not, then I don't have a clear idea what to do, just some observations. For example, if we introduce RevRotateArray, then its reverse method can be optimized, since reverse+rotate+reverse=rotate, and we just need RevRotateArray.reverse() = RotateArray.
to wangwenyou: this is just a sample of OO design. While practically, people may not need this kind of functionality. I guess that's why jdk or jgl don't want to bother this. :)ok. Here's my solution, Babysloth said he would work out a solution later, but let's not wait for him. :)Although I still guess that there might be some complicated situation that it cannot solve. But it does solve situations like rotate.reverse.rotateNow, suppose we have the 16 observations between each two operations. I'll give a sample impl for rotate first.First of all, let's clarify some basic thoughts in my mind.To take advantage of polymorphism, it's intuitive to add the reverse, rotate, concat, slice methods to Array interface, But by doing that, we are requiring all the adapters to implement these methods too. Although we could provide an abstract class to them to inherit, subclassing is almost always a bad idea! And these methods are actually independent of the array impl. No matter it's CollectionArray, StringArray, JArray2Array, the rotate, reverse, ... remains the same. So, bridge pattern should be used here. a new interface Sequence is introduced.And here it goes:public interface Sequence extends Array { public Sequence rotate(int i); public Sequence reverse(); public Sequence slice(int start, int len); public Sequence concat(Sequence other); }class Array2Sequence implements Sequence { public Sequence rotate(int i){ return RotateSequence.decorate(this, i); } public Sequence reverse(){ return ReverseSequence.decorate(this); } public Sequence slice(int start, int len){ return SliceSequence.decorate(this, start, len); } public Sequence concat(Sequence other){ return ConcatSequence.decorate(this, other); }
public int getLength(){return arr.getLength();} public Object get(int i){return arr.get(i);} public void set(int i, Object val){arr.set(i, val);} private final Array arr; private Array2Sequence(Array arr){this.arr = arr;} public Sequence adapt(Array arr){return Array2Sequence(arr);} }class RotateSequence implements Sequence { public Sequence rotate(int i){ return seq.rotate(r+i); //rotate(i).rotate(j) == rotate(i+j) } public Sequence reverse(){ return RotateSequence.decorate(seq.reverse(), -r); //rotate(i).reverse() == reverse().rotate(-i) } public Sequence slice(int start, int len){ if(r>=0 && start >= r && start+len < seq.getLength()-r || r<0 && start +len < seq.getLength() + r) {//r>0 means clockwise return seq.slice(start-r, len); //if the slice does not overlap with the rollover part, simply get the slice. } else { return SliceSequence.decorate(this, start, len); } } public Sequence concat(Sequence other){ ConcatSequence.decorate(this, other); }
private final int map(int i){return (i+r)%seq.getLength();}
public int getLength(){return seq.getLength();} public Object get(int i){return seq.get(map(i));} public void set(int i, Object val){seq.set(map(i), val);} private final Sequence seq; private RotateSequence(Sequence seq, int r){this.seq = seq; this.r = r;} public Sequence decorate(Sequence seq, int r){ if(r == 0) { return seq; } else if(r>0) { return clockwise(seq, r%seq.getLength()); } else { return anticlockwise(seq, (-r)%seq.getLength()); } } private Sequence clockwise(Sequence seq, int r) { return new RotateSequence(seq, r); } private Sequence anticlockwise(Sequence seq, int r) { return new RotateSequence(seq, -r); } }ReverseSequence, ConcatSequence, SliceSequence are similar.Specially, ReverseSequence.reverse() would be {return seq;} ReverseSequence.rotate(i) would be {return decorate(seq.rotate(-i));}
So, to do rotate(2).reverse().rotate(2).reverse() to arr, what we need to do is calling Array2Sequence.adapt(arr).rotate(2).reverse().rotate(2).reverse();And step by step, it'll reduce to 1. Array2Sequence.rotate(2).reverse().rotate(2).reverse() 2. RotateSequence(r=2) Array2Sequence .reverse().rotate(2).reverse() 3. RotateSequence(r=-2) ReverseSequence Array2Sequence .rotate(2).reverse() 4. ReverseSequence Array2Sequence .reverse() 5. Array2Sequence
Oops, to avoid negative modulo problem, the RotateSequence.map should be private final int map(int i){return (i+r+seq.getLength())%seq.getLength();}
Another fix: decorate, clockwise, anticlockwise methods should be static.
lazy evaluation doesnt means no evaluation. let's say : array a[n]; // n>m array b= a.reverse().slice(m).reverse().rotate()......can you give me a answer what b[0] is in a generic way?btw, lazy evaluation can be removed by reorder the sequence of execution. take a look at those functional languages and you will know java are lightyears behind in this area.
1. a.reverse() [0] is mapped to a[n] 2. don't know what slice(m) means, let's assume it means to cut the array to length m. then [0] is still mapped to a[n]3. calling reverse() again [0] is mapped to a[m-1]4. rotate(r) [0] is mapped to a[m-1-r]Lazy evaluation overall is a hard thing. I don't want to do graph reduction. :-)
Buddies, please look at http://www.csdn.net/Expert/TopicView1.asp?id=702325 and http://www.csdn.net/expert/topic/702/702327.xml?temp=.3666651 I can't close them without replies.
"lazy evaluation doesnt means no evaluation. " 妙语！ 给你一个非惰性的评价：）
So far, if we do some reverse-engineering, we can list the patterns that we've used in this example: 1. Adapter to wangwenyou, the reflection used in JArray2Array is only for Laziness and fast development, adapter pattern is good because you can easily unplug and plug in new adapters. reflection is not type safe and inefficient, it should be considered the last resort. so some other adapters like ObjectArray should be used instead eventually. 2. decorator 3. bridge 4. chain of responsibility (Do you agree?)See? that's why I say that you don't need to use patterns for using patterns. They'll be there smiling to you when you follow the "programming against interface, programming by contract" rule. If you happen to know the pattern names, that's fine because it's easier to communicate with others, but even if you don't know the names, so what? babysloth said he wanted to spend some time to think about it. So Let's wait for his solution, maybe he will come up with a better one. I still have a follow-up question on this Array example. But don't have an answer myself. :-( I guess babysloth might have a solution using C++. Do you guys want to discuss that? Maybe some of you can shed some light on me. (I don't have much points left though) Discuss, discuss, discuss!
Also, State pattern and immutable approach. immutable is not mentioned in gof's book, but it's really useful. normally, when you use different class to represent different state, immutable appproach can be used to vary state.
the problem is: it's a very specified case, how about a.reverse().rotate().slice(x, y)...many steps in between..rotate() ?BTW, virtual functions are faster than if-else if the numbers are large ( as switch are faster than if-else with lots of conditions).
"a.reverse().rotate().slice(x, y)...many steps in between..rotate()" But I can't give reduction for "...". :)For a.reverse().rotate().slice().rotate(), here is the reduction:Array2Sequence .reverse().rotate().slice(x, y).rotate() ReverseSequence .rotate(i).slice(x, y).rotate(j) Array2Sequence
ReverseSequence .rotate(j) RotateSequence(-i).slice(length-x, y) Array2Sequencehere, the reduction of RotateSequence.slice really depends on the values, if the slice does not overlap with the roll-over part, we simply slice, otherwise, no simplification So, if they don't overlap, the next reduction would beReverseSequence .rotate(j) SliceSequence(x2, y) Array2Sequence
ReverseSequence RotateSequence(-j) SliceSequence(x2, y) Array2SequenceOr, if they do overlap, the reduction would be: ReverseSequence .rotate(j) SliceSequence(length-x, y) RotateSequence(-i) Array2SequenceReverseSequence RotateSequence(-j) SliceSequence(length-x, y) RotateSequence(-i) Array2SequenceTo wangwenyou: reflection is not type safe. And that really hurts your OO design sometimes.
And you don't need big "if-else" in this example. when you use Object[], just create ObjectArray that adapts Object[] to Array.
wangwenyou: do you mind sharing your app's details with us, so we can know why it's not avoidable?
guys, I have a follow-up question and I don't have answer myself. please take a look at: http://www.csdn.net/expert/topic/715/715422.xml?temp=5.665225E-02
因没有时间实现，写出想法，不知是否可行，请多指教。
And how can we get the programmer's purpose?
How to get the different between below:
1. arr.slice(1, 100).slice(2, 10);
2. temp = arr.slice(1, 100);doSome(temp);temp.slice(2, 10);I consider that the work of this aspect could be done by the java compiler,do u think?
http://www.csdn.net/expert/topic/701/701403.xml?temp=.7961542
I don't quite understand your approach.
If it only does "连续出现两次相同的状态"
Can it work with arr.rotate(2).reverse().rotate(2)?To cocia(高亚):
what do you mean by "what the programmer want"?
Actually whatever we do, it should not affect the observable behavior of the array. i.e. the solution should provide the same functionality as the simple decorator approach. The only difference is performance and memory usage.
the methods don't have to be mutable.
i.e.
if arr is [1, 2, 3]
after calling arr2 = arr.reverse()
arr2 is [3, 2, 1], arr can still be [1, 2, 3]
我之所以限定“连续出现两次相同的状态”是因为某些状态是不可逆的，这需要一个特别智能化的判断逻辑。JGL的设计里好像也没有考虑到这种程度，静待高手解决或你的答案：）
My mean is that we cann't get the nead info from the java expression:
arr.slice(1, 100).rotate(2).slice(2, 10).rotate(2);
Will u keep the status after calling each mothed?
For the rest, I'm not sure, it depends on whether two successive operations can be simplified into one. If yes, then it's easy like the ReverseArray. Otherwise we'll need some serious consideration, since introducing new Arrays that embed two successive operations is a lot of work, and their reverse/slice/etc methods will need to be optimized too.
Anyway, the general idea is that the reverse/slice/etc methods of the ReverseArray/SliceArray/etc classes represent two successive operations, and you should optimize accordingly.
My solution may not be the best one.
Basically, we should get some observations of the interactions between each two operations.
i.e.
1. arr.rotate(i).reverse() == arr.reverse().rotate(-i)
2. arr.rotate(i).rotate(j) == arr.rotate(i+j)
3. arr.reverse().reverse() == arr
4. arr.rotate(i).slice(j, k) == arr.slice(i+j, k)
if the slice does not overlap with the roll-over part; no simplification otherwise5. arr.slice(i, j).slice(k, l) == arr.slice(i+k, l)
if l <= j, exception otherwise
6. arr.concat(arr2).slice(i, j) == arr.slice(i, j)
if i<arr.length && i+j<arr.length; arr2.slice(i-arr.length, j) if i>arr.length; no simplification otherwise
......
when I say arr2=arr.reverse();
and arr is [1, 2, 3], arr2 is [3, 2, 1]
it does not have to be an array copy operation.the [1, 2, 3] or [3, 2, 1] is only determined by your Array implementation.In other words, arr only appears as [1, 2, 3] when you call arr.get(0), arr.get(1), arr.get(2) respectively, arr2 only appears as [3, 2,1] when you call arr2.get(0), arr2.get(1), arr2.get(2) respectively.
"Anyway, the general idea is that the reverse/slice/etc methods of the ReverseArray/SliceArray/etc classes represent two successive operations, and you should optimize accordingly."
don't quite follow you.
do you mean you need classes like RevRotateArray, RotateRevArray, RevSliceArray etc?
even that, how do you optimize revRotate + RotateRev?
如果JDK或JGL的设计也能智能化到这程度就好了。
佩服！
I guess that's why jdk or jgl don't want to bother this. :)ok. Here's my solution, Babysloth said he would work out a solution later, but let's not wait for him. :)Although I still guess that there might be some complicated situation that it cannot solve.
But it does solve situations like rotate.reverse.rotateNow, suppose we have the 16 observations between each two operations. I'll give a sample impl for rotate first.First of all, let's clarify some basic thoughts in my mind.To take advantage of polymorphism, it's intuitive to add the reverse, rotate, concat, slice methods to Array interface,
But by doing that, we are requiring all the adapters to implement these methods too. Although we could provide an abstract class to them to inherit, subclassing is almost always a bad idea!
And these methods are actually independent of the array impl. No matter it's CollectionArray, StringArray, JArray2Array,
the rotate, reverse, ... remains the same.
So, bridge pattern should be used here. a new interface Sequence is introduced.And here it goes:public interface Sequence extends Array
{
public Sequence rotate(int i);
public Sequence reverse();
public Sequence slice(int start, int len);
public Sequence concat(Sequence other);
}class Array2Sequence implements Sequence
{
public Sequence rotate(int i){
return RotateSequence.decorate(this, i);
}
public Sequence reverse(){
return ReverseSequence.decorate(this);
}
public Sequence slice(int start, int len){
return SliceSequence.decorate(this, start, len);
}
public Sequence concat(Sequence other){
return ConcatSequence.decorate(this, other);
}
public int getLength(){return arr.getLength();}
public Object get(int i){return arr.get(i);}
public void set(int i, Object val){arr.set(i, val);}
private final Array arr;
private Array2Sequence(Array arr){this.arr = arr;}
public Sequence adapt(Array arr){return Array2Sequence(arr);}
}class RotateSequence implements Sequence
{
public Sequence rotate(int i){
return seq.rotate(r+i);
//rotate(i).rotate(j) == rotate(i+j)
}
public Sequence reverse(){
return RotateSequence.decorate(seq.reverse(), -r);
//rotate(i).reverse() == reverse().rotate(-i)
}
public Sequence slice(int start, int len){
if(r>=0 && start >= r && start+len < seq.getLength()-r
||
r<0 && start +len < seq.getLength() + r)
{//r>0 means clockwise
return seq.slice(start-r, len);
//if the slice does not overlap with the rollover part, simply get the slice.
}
else
{
return SliceSequence.decorate(this, start, len);
}
}
public Sequence concat(Sequence other){
ConcatSequence.decorate(this, other);
}
private final int map(int i){return (i+r)%seq.getLength();}
public int getLength(){return seq.getLength();}
public Object get(int i){return seq.get(map(i));}
public void set(int i, Object val){seq.set(map(i), val);}
private final Sequence seq;
private RotateSequence(Sequence seq, int r){this.seq = seq; this.r = r;}
public Sequence decorate(Sequence seq, int r){
if(r == 0)
{
return seq;
}
else if(r>0)
{
return clockwise(seq, r%seq.getLength());
}
else
{
return anticlockwise(seq, (-r)%seq.getLength());
}
}
private Sequence clockwise(Sequence seq, int r)
{
return new RotateSequence(seq, r);
}
private Sequence anticlockwise(Sequence seq, int r)
{
return new RotateSequence(seq, -r);
}
}ReverseSequence, ConcatSequence, SliceSequence are similar.Specially, ReverseSequence.reverse() would be
{return seq;}
ReverseSequence.rotate(i) would be
{return decorate(seq.rotate(-i));}
So, to do rotate(2).reverse().rotate(2).reverse() to arr, what we need to do is calling
Array2Sequence.adapt(arr).rotate(2).reverse().rotate(2).reverse();And step by step, it'll reduce to
1. Array2Sequence.rotate(2).reverse().rotate(2).reverse()
2. RotateSequence(r=2)
Array2Sequence
.reverse().rotate(2).reverse()
3. RotateSequence(r=-2)
ReverseSequence
Array2Sequence
.rotate(2).reverse()
4. ReverseSequence
Array2Sequence
.reverse()
5. Array2Sequence
the RotateSequence.map should be
private final int map(int i){return (i+r+seq.getLength())%seq.getLength();}
decorate, clockwise, anticlockwise methods should be static.
let's say :
array a[n]; // n>m
array b= a.reverse().slice(m).reverse().rotate()......can you give me a answer what b[0] is in a generic way?btw, lazy evaluation can be removed by reorder the sequence of execution. take a look at those functional languages and you will know java are lightyears behind in this area.
[0] is mapped to a[n]
2. don't know what slice(m) means, let's assume it means to cut the array to length m. then [0] is still mapped to a[n]3. calling reverse() again
[0] is mapped to a[m-1]4. rotate(r)
[0] is mapped to a[m-1-r]Lazy evaluation overall is a hard thing. I don't want to do graph reduction. :-)
http://www.csdn.net/Expert/TopicView1.asp?id=702325
and
http://www.csdn.net/expert/topic/702/702327.xml?temp=.3666651
I can't close them without replies.
妙语！
给你一个非惰性的评价：）
1. Adapter
to wangwenyou, the reflection used in JArray2Array is only for Laziness and fast development, adapter pattern is good because you can easily unplug and plug in new adapters. reflection is not type safe and inefficient, it should be considered the last resort. so some other adapters like ObjectArray should be used instead eventually.
2. decorator
3. bridge
4. chain of responsibility (Do you agree?)See? that's why I say that you don't need to use patterns for using patterns. They'll be there smiling to you when you follow the "programming against interface, programming by contract" rule.
If you happen to know the pattern names, that's fine because it's easier to communicate with others, but even if you don't know the names, so what?
babysloth said he wanted to spend some time to think about it. So Let's wait for his solution, maybe he will come up with a better one.
I still have a follow-up question on this Array example. But don't have an answer myself. :-(
I guess babysloth might have a solution using C++. Do you guys want to discuss that? Maybe some of you can shed some light on me. (I don't have much points left though)
Discuss, discuss, discuss!
immutable is not mentioned in gof's book, but it's really useful.
normally, when you use different class to represent different state, immutable appproach can be used to vary state.
1、如JDBC必须用Class.forName()来实例化一个不确定的类一样，我封装了一些东西，必须如此施为。
2、长篇累牍的if else是破坏代码清晰和可维护性一个大敌，我只能牺牲性能，来取得维护的方便。
毕竟，OO的精神首先强调的不是性能，而是清晰可维护。对于目前的B/S应用而言，Server端消耗的一小段时间片，对于窄带时代漫长的传输消耗来说，是微不足道的。：）
个人意见，还望赐教
a.reverse().rotate().slice(x, y)...many steps in between..rotate() ?BTW, virtual functions are faster than if-else if the numbers are large ( as switch are faster than if-else with lots of conditions).
But I can't give reduction for "...". :)For
a.reverse().rotate().slice().rotate(), here is the reduction:Array2Sequence .reverse().rotate().slice(x, y).rotate()
ReverseSequence .rotate(i).slice(x, y).rotate(j)
Array2Sequence
ReverseSequence slice(x, y).rotate(j)
RotateSequence(-i)
Array2Sequence
ReverseSequence .rotate(j)
RotateSequence(-i).slice(length-x, y)
Array2Sequencehere, the reduction of RotateSequence.slice really depends on the values, if the slice does not overlap with the roll-over part, we simply slice, otherwise, no simplification
So, if they don't overlap, the next reduction would beReverseSequence .rotate(j)
SliceSequence(x2, y)
Array2Sequence
ReverseSequence
RotateSequence(-j)
SliceSequence(x2, y)
Array2SequenceOr, if they do overlap, the reduction would be:
ReverseSequence .rotate(j)
SliceSequence(length-x, y)
RotateSequence(-i)
Array2SequenceReverseSequence
RotateSequence(-j)
SliceSequence(length-x, y)
RotateSequence(-i)
Array2SequenceTo wangwenyou:
reflection is not type safe. And that really hurts your OO design sometimes.
do you mind sharing your app's details with us, so we can know why it's not avoidable?
please take a look at:
http://www.csdn.net/expert/topic/715/715422.xml?temp=5.665225E-02
http://www.csdn.net/expert/topic/717/717381.xml?temp=.949093