我有一组坐标数据（估计有过万个坐标），其中含有的一些坐标是以三个为一组可以组成品字形，倒品字形等（就是两个点在一个直线上，另外一个点在该直线的垂线上）。已知垂直的这两条线的长度，将组成品字形的坐标以组为单位分离出来。
目前我用的是遍历的方法，方式要循环坐标个数的3次方个，对于大数据量情况下不合适（用户等待时间太长了）。我认为其实可以用两次循环就可以搞定的（甚至一次），但是想不出简单的方法。大家能否给个思路呢？



-- 
My Blog >> http://leejd.cndev.org
My QQ >> 9847243

既然已经知道了两条直线的长度，那么根据解析几何的知识，可以通过一个顶点，算出另外两个点的轨迹方程，你循环的时候，只要遍历一次坐标，遍历到一个点的时候判断其他是否有两点分别在这两个方程上，这样循环层数就变成两层了，如果是壹千个点，那么要循环2000000次，而你以前要循环1000000000次，这样应该快了不少吧，注意的是方程每次要转换到新坐标系中。

在 06-7-7，Gerald Lee<leejd80 at gmail.com> 写道：
> 我有一组坐标数据（估计有过万个坐标），其中含有的一些坐标是以三个为一组可以组成品字形，倒品字形等（就是两个点在一个直线上，另外一个点在该直线的垂线上）。已知垂直的这两条线的长度，将组成品字形的坐标以组为单位分离出来。
> 目前我用的是遍历的方法，方式要循环坐标个数的3次方个，对于大数据量情况下不合适（用户等待时间太长了）。我认为其实可以用两次循环就可以搞定的（甚至一次），但是想不出简单的方法。大家能否给个思路呢？
>
>
>
> --
> My Blog >> http://leejd.cndev.org
> My QQ >> 9847243
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>

因为这个品字形可以是四个方向的，既单口的那个可以在上面，左边，下面，右边，所以得出的坐标应该是8个（4组），但是实际可能会遇到两个点不是一组的情况。还有，这8个点逐个验证循环量也是增加不少的了


2006/7/8, WhiteFox <wyh817 at gmail.com>:
> 既然已经知道了两条直线的长度，那么根据解析几何的知识，可以通过一个顶点，算出另外两个点的轨迹方程，你循环的时候，只要遍历一次坐标，遍历到一个点的时候判断其他是否有两点分别在这两个方程上，这样循环层数就变成两层了，如果是壹千个点，那么要循环2000000次，而你以前要循环1000000000次，这样应该快了不少吧，注意的是方程每次要转换到新坐标系中。
>
> 在 06-7-7，Gerald Lee<leejd80 at gmail.com> 写道：
> > 我有一组坐标数据（估计有过万个坐标），其中含有的一些坐标是以三个为一组可以组成品字形，倒品字形等（就是两个点在一个直线上，另外一个点在该直线的垂线上）。已知垂直的这两条线的长度，将组成品字形的坐标以组为单位分离出来。
> > 目前我用的是遍历的方法，方式要循环坐标个数的3次方个，对于大数据量情况下不合适（用户等待时间太长了）。我认为其实可以用两次循环就可以搞定的（甚至一次），但是想不出简单的方法。大家能否给个思路呢？
> >
> >
> >
> > --
> > My Blog >> http://leejd.cndev.org
> > My QQ >> 9847243
> >
> > _______________________________________________
> > python-chinese
> > Post: send python-chinese at lists.python.cn
> > Subscribe: send subscribe to python-chinese-request at lists.python.cn
> > Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> > Detail Info: http://python.cn/mailman/listinfo/python-chinese
> >
> >
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>


-- 
My Blog >> http://leejd.cndev.org
My QQ >> 9847243

还是用WhiteFox的思路，第一层循环是免不了的，第二层循环本质上是一个查找过程，那么可以通过特别的数据结构加快查找的速度。
1. 如果坐标是整点，而且范围有限，那么可以开两个一维大数组（分别对x和y坐标）作记录，这样查找时间复杂度是O(1)，总时间复杂度是O(n)。
2. 否则的话，可以用二叉排序树，这样查找时间复杂度是O(log(n))，总时间复杂度是O(n*log(n))。
3. 如果1所需要的空间太大，而2还是不够快的话，那么可以用一个足够大的哈希表，速度介于两者之间。自己调整一下哈希函数，速度可以达到近似O(n)。

On 7/8/06, Gerald Lee <leejd80 at gmail.com> wrote:
>
>
> 因为这个品字形可以是四个方向的，既单口的那个可以在上面，左边，下面，右边，所以得出的坐标应该是8个（4组），但是实际可能会遇到两个点不是一组的情况。还有，这8个点逐个验证循环量也是增加不少的了
>
>
> 2006/7/8, WhiteFox <wyh817 at gmail.com>:
> >
> 既然已经知道了两条直线的长度，那么根据解析几何的知识，可以通过一个顶点，算出另外两个点的轨迹方程，你循环的时候，只要遍历一次坐标，遍历到一个点的时候判断其他是否有两点分别在这两个方程上，这样循环层数就变成两层了，如果是壹千个点，那么要循环2000000次，而你以前要循环1000000000次，这样应该快了不少吧，注意的是方程每次要转换到新坐标系中。
> >
> > 在 06-7-7，Gerald Lee<leejd80 at gmail.com> 写道：
> > >
> 我有一组坐标数据（估计有过万个坐标），其中含有的一些坐标是以三个为一组可以组成品字形，倒品字形等（就是两个点在一个直线上，另外一个点在该直线的垂线上）。已知垂直的这两条线的长度，将组成品字形的坐标以组为单位分离出来。
> > >
> 目前我用的是遍历的方法，方式要循环坐标个数的3次方个，对于大数据量情况下不合适（用户等待时间太长了）。我认为其实可以用两次循环就可以搞定的（甚至一次），但是想不出简单的方法。大家能否给个思路呢？
> > >
> > >
> > >
> > > --
> > > My Blog >> http://leejd.cndev.org
> > > My QQ >> 9847243
> > >
> > > _______________________________________________
> > > python-chinese
> > > Post: send python-chinese at lists.python.cn
> > > Subscribe: send subscribe to python-chinese-request at lists.python.cn
> > > Unsubscribe: send unsubscribe to
> python-chinese-request at lists.python.cn
> > > Detail Info: http://python.cn/mailman/listinfo/python-chinese
> > >
> > >
> >
> > _______________________________________________
> > python-chinese
> > Post: send python-chinese at lists.python.cn
> > Subscribe: send subscribe to python-chinese-request at lists.python.cn
> > Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> > Detail Info: http://python.cn/mailman/listinfo/python-chinese
> >
> >
>
>
> --
> My Blog >> http://leejd.cndev.org
> My QQ >> 9847243
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060708/63d742c6/attachment.htm