Python论坛  - 讨论区

标题:[python-chinese] 请教一个计数算法

2007年01月09日 星期二 17:49

Leo Jay python.leojay在gmail.com
星期二 一月 9 17:49:59 HKT 2007

On 1/9/07, heyuqi <yuqi.he在gmail.com> wrote:
>
> > 其次,堆排的时间复杂度是O(nlogn)没有错,但是,取前10个的时间复杂度并不是O(10logn)
> > 而应该是O(n),确切的说大概是O((n-10)*log(10)),注:所有log均以2为底
>
> 不对吧,若一个数组 array[n] 是堆,从中删除一个数据,并使用后来的 array[n-1]仍是堆,这种算法的时候复杂度为 O(logn)
>
> 这是我们课后练习的一道题,以前证过,现在一时想不起了。只能把结果写出来
>

你的前提是array已经是一个堆了。但现在的情况程序里没有堆啊。
如果先用堆排把所有数都排一遍,那不又是一个O(nlogn)吗?

而我说的是从一个无序的数组中取前10个最大的元素的复杂度是O(n)

-- 
Best Regards,
Leo Jay

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月09日 星期二 17:57

heyuqi yuqi.he在gmail.com
星期二 一月 9 17:57:40 HKT 2007

On 1/9/07, Leo Jay <python.leojay at gmail.com> wrote:
>
>
> 你的前提是array已经是一个堆了。但现在的情况程序里没有堆啊。
> 如果先用堆排把所有数都排一遍,那不又是一个O(nlogn)吗?


从堆中删除一个数据,剩下来的就不是堆了,还要重排一次。

而我说的是从一个无序的数组中取前10个最大的元素的复杂度是O(n)


能给个例子我看看吗?我想不到如何实现。
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://python.cn/pipermail/python-chinese/attachments/20070109/b64994a3/attachment.htm 

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月09日 星期二 19:41

Leo Jay python.leojay在gmail.com
星期二 一月 9 19:41:29 HKT 2007

On 1/9/07, heyuqi <yuqi.he在gmail.com> wrote:
> On 1/9/07, Leo Jay <python.leojay在gmail.com> wrote:
> >
> > 你的前提是array已经是一个堆了。但现在的情况程序里没有堆啊。
> > 如果先用堆排把所有数都排一遍,那不又是一个O(nlogn)吗?
>
> 从堆中删除一个数据,剩下来的就不是堆了,还要重排一次。
>
> > 而我说的是从一个无序的数组中取前10个最大的元素的复杂度是O(n)
>
> 能给个例子我看看吗?我想不到如何实现。
>

堆化的复杂度就是O(n)啊,如果堆化完了之后再全部排序就是O(nlogn),
如果不全部排序,只取前10个,那复杂度还是O(n)啊。不会是O(log(n))的


-- 
Best Regards,
Leo Jay

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月09日 星期二 20:34

Yunfeng Tao taoyfeng在gmail.com
星期二 一月 9 20:34:10 HKT 2007

建堆怎么可能O(n)?你写个程序自己跑跑看就知道了,O(nlogn)。理论上讲,
log1+log2+...+logn=O(nlogn)
这个问题有特殊性,因为楼主只要10个最大的,所以整个堆只要保留上面10层就可以了。于是用堆方法可以降到O(n),但常系数约在20-30,远超过半个快速排序的3。

2007/1/9, Leo Jay <python.leojay在gmail.com>:
> 堆化的复杂度就是O(n)啊,如果堆化完了之后再全部排序就是O(nlogn),
> 如果不全部排序,只取前10个,那复杂度还是O(n)啊。不会是O(log(n))的

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月09日 星期二 20:47

Yunfeng Tao taoyfeng在gmail.com
星期二 一月 9 20:47:09 HKT 2007

令f(A,k)计算A中前k大的元素。
随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。
如果|B|=k,B就是我们所求的,stop;
如果k<|B|,递归 f(B,k);
如果k>|B|,首先B是我们所求的一部分,然后递归f(C,k-|B|)。
严格的分析时间复杂度比较麻烦,粗略地讲,期望上|B|=|C|=0.5|A|,所以期望时间复杂度约为|A|+0.5|A|+0.25|A|+...这是个简单的等比数列求和问题,解是2|A|。刚才我说了,这个计算很粗略,很不严格。精确的期望值大约在3|A|左右。

在 07-1-9,heyuqi<yuqi.he在gmail.com> 写道:
> 半个快速排序?可以实现需求吗?
>
> 在我这里快速排序也叫分划排序,每一趟排序都确定一个数的位置,使它左边的数都小于它,右边的数都大于它。而一趟排序的时间复杂度应该是
> O(n),每个数都要扫描一遍。
>

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月09日 星期二 21:12

Leo Jay python.leojay在gmail.com
星期二 一月 9 21:12:38 HKT 2007

On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote:
> 建堆怎么可能O(n)?你写个程序自己跑跑看就知道了,O(nlogn)。理论上讲,
> log1+log2+...+logn=O(nlogn)
> 这个问题有特殊性,因为楼主只要10个最大的,所以整个堆只要保留上面10层就可以了。于是用堆方法可以降到O(n),但常系数约在20-30,远超过半个快速排序的3。
>


理论的东西怎么可能是写个程序跑跑看就能看出结果的?

你可以看看<> 6.4章的Building a heap.
里面写得很清楚,
the running time of BUILD-MAX-HEAP can be bounded as O(n)


-- 
Best Regards,
Leo Jay

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月09日 星期二 22:21

heyuqi yuqi.he在gmail.com
星期二 一月 9 22:21:07 HKT 2007

On 1/9/07, Leo Jay <python.leojay at gmail.com> wrote:
>
> On 1/9/07, heyuqi <yuqi.he at gmail.com> wrote:
> > On 1/9/07, Leo Jay <python.leojay at gmail.com> wrote:
> > >
> > > 你的前提是array已经是一个堆了。但现在的情况程序里没有堆啊。
> > > 如果先用堆排把所有数都排一遍,那不又是一个O(nlogn)吗?
> >
> > 从堆中删除一个数据,剩下来的就不是堆了,还要重排一次。
> >
> > > 而我说的是从一个无序的数组中取前10个最大的元素的复杂度是O(n)
> >
> > 能给个例子我看看吗?我想不到如何实现。
> >
>
> 堆化的复杂度就是O(n)啊,如果堆化完了之后再全部排序就是O(nlogn),
> 如果不全部排序,只取前10个,那复杂度还是O(n)啊。不会是O(log(n))的


:P 现在是晕头了,把前面的也忘掉了

to Yunfeng Tao,O(n) 应该是这样来的:
i:1->n/2 累加 log(n/i) = 取整(n/2) * logn - log( 取整( n/2 )! )

由一个叫 Stirling 公式知上式 = O( n )

不过 Stirling 公式是什么就不知道 ;-)



On 1/9/07, Yunfeng Tao <taoyfeng at gmail.com> wrote:
>
> 令f(A,k)计算A中前k大的元素。
> 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。


晕,你这里假充的数据都已经是有序了,这种情况使用快速排序会有最坏的时间复杂度的!

你说随便挑一个元素 x,但是在没有进行过排序的数据中,你是无法保证 B 中元素一定比 x 大,C 中元素一定小于等于 x 的。

要针对 x 进行过一趟快速排序,这时候 x 所处的位子才是你假充的情况。x 才是用来分割 B & C 的。

这种方法是有序表查找的方法,类似二分查找和 Fibonacci 查找
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://python.cn/pipermail/python-chinese/attachments/20070109/d060d87b/attachment.html 

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月10日 星期三 09:26

麦田守望者 qcxhome在gmail.com
星期三 一月 10 09:26:42 HKT 2007

On 1/4/07, daifei <bonycamel at gmail.com> wrote:
>
>
>
>
>
> 各位好,我要实现以下需求,感觉python可能有现成的方法,请各位指教。
>
>
>
> 在一个list中,有大量整数(10000个或更多),例如:[1,1,3,3,9999,9,3,512,1,8,9,……]
>
> 我需要写一个算法,统计这个数字list中出现次数最多的10个整数,分别存到变量i1-i10。
>
>
>
> 用一般的循环应该可以实现,但是效率比较差,也比较麻烦,请问python有什么现成的实现方式吗?谢谢。
>

不用循环用什么呢?


-- 
GoogleTalk: qcxhome at gmail.com
MSN: qcxhome at hotmail.com
My Space: tkdchen.spaces.live.com
BOINC: boinc.berkeley.edu
中国分布式计算总站: www.equn.com

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月10日 星期三 09:56

Yunfeng Tao taoyfeng在gmail.com
星期三 一月 10 09:56:40 HKT 2007

"假充"?什么东西?
注意,我挑的是一个元素,不是一个位置。再去温习下快速排序吧。

在 07-1-9,heyuqi<yuqi.he在gmail.com> 写道:
> On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote:
> > 令f(A,k)计算A中前k大的元素。
> > 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。
>
> 晕,你这里假充的数据都已经是有序了,这种情况使用快速排序会有最坏的时间复杂度的!
>
> 你说随便挑一个元素 x,但是在没有进行过排序的数据中,你是无法保证 B 中元素一定比 x 大,C 中元素一定小于等于 x 的。
>
> 要针对 x 进行过一趟快速排序,这时候 x 所处的位子才是你假充的情况。x 才是用来分割 B & C 的。
>
> 这种方法是有序表查找的方法,类似二分查找和 Fibonacci 查找
>

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月10日 星期三 10:57

Leo Jay python.leojay在gmail.com
星期三 一月 10 10:57:06 HKT 2007

On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote:
> 令f(A,k)计算A中前k大的元素。
> 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。
> 如果|B|=k,B就是我们所求的,stop;
> 如果k<|B|,递归 f(B,k);
> 如果k>|B|,首先B是我们所求的一部分,然后递归f(C,k-|B|)。
> 严格的分析时间复杂度比较麻烦,粗略地讲,期望上|B|=|C|=0.5|A|,所以期望时间复杂度约为|A|+0.5|A|+0.25|A|+...这是个简单的等比数列求和问题,解是2|A|。刚才我说了,这个计算很粗略,很不严格。精确的期望值大约在3|A|左右。
>

你用了类似快排的思路,所以会有跟快排一样的缺陷:最差情况的复杂度是O(n^2)
想像一下你第一次选中的是最小的数,第二次选中的是第二小的数,... 第i次选中第i小的数。
很明显的O(n^2)

楼主的应用,还是做个堆,然后取10个最大的数,这样复杂度比较有保证,O(n)。

-- 
Best Regards,
Leo Jay

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月10日 星期三 11:08

Yunfeng Tao taoyfeng在gmail.com
星期三 一月 10 11:08:08 HKT 2007

这个是我记错了,确实是O(n)

2007/1/9, Leo Jay <python.leojay在gmail.com>:
> On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote:
> > 建堆怎么可能O(n)?你写个程序自己跑跑看就知道了,O(nlogn)。理论上讲,
> > log1+log2+...+logn=O(nlogn)
> > 这个问题有特殊性,因为楼主只要10个最大的,所以整个堆只要保留上面10层就可以了。于是用堆方法可以降到O(n),但常系数约在20-30,远超过半个快速排序的3。
> >
>
>
> 理论的东西怎么可能是写个程序跑跑看就能看出结果的?
>
> 你可以看看<> 6.4章的Building a heap.
> 里面写得很清楚,
> the running time of BUILD-MAX-HEAP can be bounded as O(n)
>
>
> --
> Best Regards,
> Leo Jay
> _______________________________________________
> python-chinese
> Post: send python-chinese在lists.python.cn
> Subscribe: send subscribe to python-chinese-request在lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request在lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月10日 星期三 11:38

Yunfeng Tao taoyfeng在gmail.com
星期三 一月 10 11:38:17 HKT 2007

不错,最坏情况是O(n^2)。学界有大量的工作投入到如何不让快排的最坏情况出现,比较简单的方法是:随机选择元素x。
快排有许多非常好的优点:第一它快,期望时间复杂度O(nlogn),O(n^2)的情况几乎不会出现,而且常数非常小;第二它容易实现,不容易写错。所以很多语言(比如C)的类库提供的排序方法还是快排。

2007/1/10, Leo Jay <python.leojay在gmail.com>:
> On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote:
> > 令f(A,k)计算A中前k大的元素。
> > 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。
> > 如果|B|=k,B就是我们所求的,stop;
> > 如果k<|B|,递归 f(B,k);
> > 如果k>|B|,首先B是我们所求的一部分,然后递归f(C,k-|B|)。
> > 严格的分析时间复杂度比较麻烦,粗略地讲,期望上|B|=|C|=0.5|A|,所以期望时间复杂度约为|A|+0.5|A|+0.25|A|+...这是个简单的等比数列求和问题,解是2|A|。刚才我说了,这个计算很粗略,很不严格。精确的期望值大约在3|A|左右。
> >
>
> 你用了类似快排的思路,所以会有跟快排一样的缺陷:最差情况的复杂度是O(n^2)
> 想像一下你第一次选中的是最小的数,第二次选中的是第二小的数,... 第i次选中第i小的数。
> 很明显的O(n^2)
>
> 楼主的应用,还是做个堆,然后取10个最大的数,这样复杂度比较有保证,O(n)。
>
> --
> Best Regards,
> Leo Jay
> _______________________________________________
> python-chinese
> Post: send python-chinese在lists.python.cn
> Subscribe: send subscribe to python-chinese-request在lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request在lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月10日 星期三 20:56

swordsp sparas2006在gmail.com
星期三 一月 10 20:56:07 HKT 2007

On 1/10/07, Yunfeng Tao <taoyfeng at gmail.com> wrote:
>
> 不错,最坏情况是O(n^2)。学界有大量的工作投入到如何不让快排的最坏情况出现,比较简单的方法是:随机选择元素x。
>
> 快排有许多非常好的优点:第一它快,期望时间复杂度O(nlogn),O(n^2)的情况几乎不会出现,而且常数非常小;第二它容易实现,不容易写错。所以很多语言(比如C)的类库提供的排序方法还是快排。



试着写了一个完整的实现,包括堆和"半快排"两种算法。
几点想法:
1. 算法的前半部分(计算elements),感觉还是 d[x] = d.get(x, 0) + 1 的方法最好,简洁且高效
2. 本来想自己写一个堆的,不过发现标准库中的heapq已经实现的很漂亮了,就偷懒直接用了。
3.
快排的实现比想象中麻烦,我调了不少时间。主要是这里partition函数的实现需要特别注意,某些写法对于单纯的排序没有问题,但在这个场景下就会出错(比如遇到重复元素时会导致死循坏)。
4. 时间复杂度和大家讨论的结果一样,怎么写都是O(n),区别只在常数上。
5. 因为heapq有c的实现,所以直接比较的话堆方法速度肯定比纯python的半快排方法要快,不过这并不说明堆的算法常数上更优。详细的测试我还没做。
6.
感觉python写这种基础的算法优势不大,因为效率方面的顾虑很多pythonic的写法都用不上,感觉和写c区别不大。当然也可能只是我功力还不够...

代码如下:

import heapq
import random

class Element(object):

    def __init__(self, key, value):
        self.key = key
        self.value = value

    # override __cmp__ method so that we can implement generally klargest
method
    def __cmp__(self, other):
        return self.key.__cmp__(other.key)

    def __repr__(self):
        return (self.key, self.value).__repr__()

def klargest_by_heap(array, k):
    heapq.heapify(array)
    return heapq.nlargest(k, array)

def partition(array, start, end):
    pivot_index = random.randint(start, end)
    array[start], array[pivot_index] = array[pivot_index], array[start]
    i, j = start, end
    while True:
        while i <= j and array[i] >= array[start]:
            i += 1
        while i <= j and array[j] < array[start]:
            j -= 1
        if i > j:
            break
        array[i], array[j] = array[j], array[i]
    pivot_index = i - 1

    # can be ignored in normal quicksort, but MUST do it in this case
    array[pivot_index], array[start] = array[start], array[pivot_index]

    return pivot_index

def klargest_by_quicksort(array, k):
    start, end, split = 0, len(array) - 1, len(array) - 1
    while split != k - 1:
        split = partition(array, start, end)
        if split < k - 1:
            start = split + 1
        elif split > k - 1:
            end = split - 1
    return array[:k]

def k_most_frequently(array, k):
    d = {}
    for x in array:
        d[x] = d.get(x,0) + 1
    elements = [Element(count, value) for (value, count) in d.items()]
    return [e.value for e in klargest(elements, k)]

if __name__ == "__main__":
    a = [1,5,4,4,2,2,4]

    klargest = klargest_by_heap
    print k_most_frequently(a, 2)

    klargest = klargest_by_quicksort
    print k_most_frequently(a, 2)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://python.cn/pipermail/python-chinese/attachments/20070110/01721d72/attachment.htm 

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月11日 星期四 09:58

Yunfeng Tao taoyfeng在gmail.com
星期四 一月 11 09:58:33 HKT 2007

在 07-1-10,swordsp<sparas2006在gmail.com> 写道:
>
> 3.
> 快排的实现比想象中麻烦,我调了不少时间。主要是这里partition函数的实现需要特别注意,某些写法对于单纯的排序没有问题,但在这个场景下就会出错(比如遇到重复元素时会导致死循坏)。
这点我也疏忽了。

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2007年01月13日 星期六 16:24

Yunfeng Tao taoyfeng在gmail.com
星期六 一月 13 16:24:25 HKT 2007

partition的实现有效率问题。如果整个array的元素全同,那么一次partition只能减少一个元素。我稍作修改如下:

def partition(array, start, end):
    pivot_index = random.randint(start, end)
    array[start], array[pivot_index] = array[pivot_index], array[start]
    i, j = start+1, end
    while i <= j:
        array[i], array[j] = array[j], array[i]
        while i <= j and array[i]+random.random()-0.5 >= array[start]:
            i += 1
        while i <= j and array[j]+random.random()-0.5 < array[start]:
            j -= 1
    pivot_index = i - 1
    array[start], array[pivot_index] = array[pivot_index], array[start]
    return pivot_index

1.对于整数a,b,如果a
b,那么"a>b+0.5,当且仅当,a>b-0.5,当且仅当,a>b"。根据这个性质,partition结束时,比array[pivot_index]大的都在pivot_index前面,小的都在后面。
2. 和array[pivot_index]等大的元素,每一个都独立地有一半概率排在前面。所以partition结束时,和array[pivot_index]等大的元素期望上有一半排在pivot_index前面。
如此一来,到达期望上的二分,避免最坏情况的出现。

在 07-1-10,swordsp<sparas2006在gmail.com> 写道:
>
>  试着写了一个完整的实现,包括堆和"半快排"两种算法。
>  几点想法:
> 1. 算法的前半部分(计算elements),感觉还是 d[x] = d.get(x, 0) + 1 的方法最好,简洁且高效
> 2. 本来想自己写一个堆的,不过发现标准库中的heapq已经实现的很漂亮了,就偷懒直接用了。
> 3.
> 快排的实现比想象中麻烦,我调了不少时间。主要是这里partition函数的实现需要特别注意,某些写法对于单纯的排序没有问题,但在这个场景下就会出错(比如遇到重复元素时会导致死循坏)。
>  4. 时间复杂度和大家讨论的结果一样,怎么写都是O(n),区别只在常数上。
> 5.
> 因为heapq有c的实现,所以直接比较的话堆方法速度肯定比纯python的半快排方法要快,不过这并不说明堆的算法常数上更优。详细的测试我还没做。
>  6.
> 感觉python写这种基础的算法优势不大,因为效率方面的顾虑很多pythonic的写法都用不上,感觉和写c区别不大。当然也可能只是我功力还不够...
>
> 代码如下:
>
>  import heapq
>  import random
>
>  class Element(object):
>
>      def __init__(self, key, value):
>          self.key = key
>          self.value = value
>
>      # override __cmp__ method so that we can implement generally klargest
> method
>      def __cmp__(self, other):
>          return self.key.__cmp__(other.key)
>
>      def __repr__(self):
>          return (self.key, self.value).__repr__()
>
>  def klargest_by_heap(array, k):
>      heapq.heapify(array)
>      return heapq.nlargest(k, array)
>
>  def partition(array, start, end):
>      pivot_index = random.randint(start, end)
>      array[start], array[pivot_index] = array[pivot_index], array[start]
>      i, j = start, end
>      while True:
>          while i <= j and array[i] >= array[start]:
>              i += 1
>          while i <= j and array[j] < array[start]:
>              j -= 1
>          if i > j:
>              break
>          array[i], array[j] = array[j], array[i]
>      pivot_index = i - 1
>
>      # can be ignored in normal quicksort, but MUST do it in this case
>      array[pivot_index], array[start] = array[start], array[pivot_index]
>
>      return pivot_index
>
>  def klargest_by_quicksort(array, k):
>      start, end, split = 0, len(array) - 1, len(array) - 1
>      while split != k - 1:
>          split = partition(array, start, end)
>          if split < k - 1:
>              start = split + 1
>          elif split > k - 1:
>              end = split - 1
>      return array[:k]
>
>  def k_most_frequently(array, k):
>      d = {}
>      for x in array:
>          d[x] = d.get(x,0) + 1
>      elements = [Element(count, value) for (value, count) in d.items()]
>      return [e.value for e in klargest(elements, k)]
>
>  if __name__ == "__main__":
>      a = [1,5,4,4,2,2,4]
>
>      klargest = klargest_by_heap
>      print k_most_frequently(a, 2)
>
>      klargest = klargest_by_quicksort
>      print k_most_frequently(a, 2)
>
> _______________________________________________
> python-chinese
> Post: send python-chinese在lists.python.cn
> Subscribe: send subscribe to
> python-chinese-request在lists.python.cn
> Unsubscribe: send unsubscribe to
> python-chinese-request在lists.python.cn
> Detail Info:
> http://python.cn/mailman/listinfo/python-chinese
>

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

如下红色区域有误,请重新填写。

    你的回复:

    请 登录 后回复。还没有在Zeuux哲思注册吗?现在 注册 !

    Zeuux © 2025

    京ICP备05028076号