在数组 MIPS 中查找第 K 个不同的元素
Finding Kth distinct element in an array MIPS
我正在尝试编写与下面的 C 代码等效的 MIPS。
int arrayData[5] = { 1,2,1,3,4 };
int K = 3;
int KCtr = 0;
int result;
bool isUnique;
for (int o = 1; o < 5; o++)
{
isUnique = true;
for (int i = 0; i < o; i++)
{
if (arrayData[o] == arrayData[i])
{
isUnique = false;
break; // goto outer loop
}
}
if (isUnique)
{
KCtr++;
}
if (KCtr==K)
{
result = arrayData[o];
}
}
我想用下面的代码将结果存储在 $s1 中。
.data
Array: .word 1, 2, 4, 8, 16, 32, 64, 128
sze : .word 8
K : .word 3
.text
.globl main
main: lw $s0,K([=11=]) # K
addi $t0,$zero,0 # index for outer loop
addi $t1,$zero,0 # index for inner loop
lw $t2,sze([=11=])
lw $s1,Array([=11=])
addi $t6,$zero,0
#addi $t7,$zero,1
#t3 for array[o]
#t4 for array[i]
#t5 for unique flag
#t6 for counter to reach K
#t7 for storing 1
outerloop:
beq $t0,$t2,finish
lw $t3,Array($t0)
addi $t5,$zero,0
innerloop:
lw $t4,Array($t1)
bne $t3,$t4,else
addi $t5,$zero,1
else:
checkifunique:
beq $t5,$t7,isnotuniquebypass
addi $t6,$zero,1
isnotuniquebypass:
addi $t1,$t1,4
blt $t1,$t0,innerloop
bne $t6,$s0,notreachedKbypass
lw $s1,Array($t0)
notreachedKbypass:
addi $t0,$t0,4
b outerloop
finish:
li $v0,10
syscall
虽然我希望在 $s1 寄存器中看到 8，但我得到了 1。我的汇编代码有什么问题？
有些事情是错误的。
您的 C 代码不完整。通过检查您的 asm 代码，我能够将缺失的内容添加到 C 代码中。
您没有正确设置一些寄存器。
您还比较了数组偏移量（递增 4 的迭代变量）与数组 index/count，因此比较不起作用。
您将 KCtr 的寄存器设置为 1，而不是执行 KCtr++
的 asm 等价物
我创建了三个示例：固定的 C 代码，您的 asm 的注释版本显示了 some/most 个错误。并且，一个清理、重构和工作的版本。
这是 C 代码：
#include <stdio.h>
#if 0
int Array[] = { 1, 2, 1, 3, 4 };
#else
int Array[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
#endif
int
main(void)
{
int result;
int K = 3;
int KCtr = 0;
int count = sizeof(Array) / sizeof(Array[0]);
int uniqflg;
result = -1;
for (int o = 1; o < count; o++) {
uniqflg = 1;
for (int i = 0; i < o; i++) {
if (Array[o] == Array[i]) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
KCtr++;
if (KCtr == K) {
result = Array[o];
}
}
printf("result=%d\n",result);
return result;
}
这是注释版本：
.data
Array: .word 1,2,4,8,16,32,64,128
sze :
K :
.text
.globl main
# s1 for result
# t0 for o
# t1 for i
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t5 for unique flag
# t6 for counter to reach K (i.e. KCtr?)
# t7 for storing 1
main:
lw $s0,K([=11=]) # K
addi $t0,$zero,0 # index for outer loop
# NOTE/BUG: this is misplaced it needs to be moved to just above innerloop
addi $t1,$zero,0 # index for inner loop
lw $t2,sze([=11=]) # get array count
lw $s1,Array([=11=]) # result = Array[0]
addi $t6,$zero,0 # KCtr = 0
# NOTE/BUG: this was commented out:
addi $t7,$zero,1
outerloop:
# NOTE/BUG: based on the increment by 4 to $t0 below, this is comparing an
# offset against a count
beq $t0,$t2,finish # o < count? if no, fly
lw $t3,Array($t0) # get Array[o]
addi $t5,$zero,0 # uniqflg = 0
innerloop:
lw $t4,Array($t1) # get Array[i]
bne $t3,$t4,inner_neq # Array[o] == Array[i]? if no, fly
# NOTE/BUG: this is just setting one (i.e. KCtr = 1 instead of KCtr++)
addi $t5,$zero,1 # uniqflg = 1
inner_neq:
checkifunique:
beq $t5,$t7,notuniq # ???
addi $t6,$zero,1
notuniq:
addi $t1,$t1,4 # advance array offset
# NOTE/BUG: this compares an array offset against an index
blt $t1,$t0,innerloop # at end? if no, loop
bne $t6,$s0,inner_next # KCtr == K? if no, interate
lw $s1,Array($t0) # get better result
inner_next:
addi $t0,$t0,4 # advance o [as offset]
b outerloop
finish:
li $v0,10
syscall
这是重构后的版本。它与您的有所不同，因为为了使其正常工作，我对其进行了一些简化。它还使用指针而不是索引或偏移量来访问数组。还要注意，一旦KCtr == K，就不需要继续循环了。
.data
Array: .word 1,2,4,8,16,32,64,128
ArrEnd:
K: .word 3
.text
.globl main
# s0 for K
# s1 for result
# t0 for o (as pointer)
# t1 for i (as pointer)
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t6 for counter to reach K (i.e. KCtr?)
main:
lw $s0,K # K
li $t6,0 # KCtr = 0
la $t2,ArrEnd # point to end of array
la $t0,Array # o = &Array[0]
lw $s1,0($t0) # result = Array[0]
outerloop:
addiu $t0,$t0,4 # advance o [as pointer]
bgeu $t0,$t2,finish # o < ArrEnd? if no, fly
lw $t3,0($t0) # get Array[o]
la $t1,Array # i = &Array[0]
innerloop:
lw $t4,0($t1) # get Array[i]
beq $t3,$t4,outerloop # Array[o] == Array[i]? if yes, not unique
addiu $t1,$t1,4 # advance array pointer for i
bltu $t1,$t0,innerloop # at end? if no, loop
# current array value is unique
addi $t6,$t6,1 # KCtr++
bne $t6,$s0,outerloop # KCtr == K? if no, wait for next unique
lw $s1,0($t0) # get better result -- no need to loop more
finish:
li $v0,1
move $a0,$s1
syscall
li $v0,10
syscall
更新：
Your code seems to be working in spim. But I didn't understand "ArrayEnd". There is no value set for it,but it works. How ?
ArrEnd 是某种 "trick"。是Array+1的最后一个元素的地址。也就是说，在C中，如果我们有int Array[5]，那么ArrEnd就是&Array[5]。
就像在 C 中一样，我们可以选择如何遍历数组。我们可以使用索引并执行：Array[i]。或者，我们可以使用 int * 指针。在 asm 中，我们可以使用从数组开始的偏移量（即 index << 2）。
让我们将 C 程序重新编码为 仅 使用指针 [而不是索引] 遍历数组。这在 C 代码中不常使用，但它对 asm 很方便。以下实际上是我的第二个 asm 示例所做的更准确的 C 代码表示：
#include <stdio.h>
#if 0
int Array[] = { 1, 2, 1, 3, 4 };
#else
int Array[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
#endif
int
main(void)
{
int result;
int K = 3;
int KCtr = 0;
int *ArrEnd = &Array[sizeof(Array) / sizeof(Array[0])];
int uniqflg;
result = -1;
for (int *o = &Array[1]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < o; i++) {
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
KCtr++;
if (KCtr == K) {
result = *o;
break;
}
}
printf("result=%d\n",result);
return result;
}
以下是 ArrEnd 的一些惯用用法：
la $s0,Array # get array address
la $s1,ArrEnd # address of array end [one past last]
subu $s2,$s1,$s0 # get byte length of array
srl $s3,$s2,2 # get array count
现在我们有了这些值，我们可以通过上述三种方法中的任何一种来遍历数组。使用偏移版本或指针版本通常可以更有效。
要了解 ArrEnd 使事情变得多么简单，请注释掉较大的数组并从 C 代码中添加较短的数组。 ArrEnd 技巧将自动调整 而无需 需要手动计算 Array
中的元素数量
更新#2：
我可能对此有误，但进一步思考，为了满足问题标题的要求，C代码[以及因此asm]可能需要更改。
我认为内部循环在查找重复项时必须扫描 整个 数组 [跳过 i == o 所在的元素]。否则可能会误报。
还有，看来原文从来不认为index 0元素是唯一的，即使是。这是因为 o 循环从索引 1 开始。
我创建了两种算法。原文如上。还有一个进行全面扫描的。我还添加了更多测试用例来说明我正在考虑的问题。
测试程序如下：
#include <stdio.h>
int Array0[] = { 1, 2, 1, 3, 4 };
int Array1[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
int Array2[] = { 1, 2, 4, 4, 8, 16, 32, 64, 128 };
int Array3[] = { 1, 2, 4, 8, 16, 32, 64, 128, 2 };
int Array4[] = { 1, 2, 4, 8, 16, 32, 64, 128, 2, 4 };
int Array5[] = { 1, 2, 3, 4, 5, 6 };
int Array6[] = { 1, 2, 3, 4, 5, 6, 1, 3 };
int K = 3;
int sepflg;
int tstno;
int
orig(int *Array,int *ArrEnd)
{
int result;
long residx;
int KCtr = 0;
int uniqflg;
result = -1;
residx = -1;
for (int *o = &Array[1]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < o; i++) {
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
printf(" orig: MATCH value=%d index=%ld\n",*o,o - Array);
KCtr++;
if (KCtr == K) {
result = *o;
residx = o - Array;
break;
}
}
printf(" orig: FINAL result=%d residx=%ld\n",result,residx);
return result;
}
int
full(int *Array,int *ArrEnd)
{
int result;
long residx;
int KCtr = 0;
int uniqflg;
result = -1;
residx = -1;
for (int *o = &Array[0]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < ArrEnd; i++) {
if (o == i)
continue;
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
printf(" full: MATCH value=%d index=%ld\n",*o,o - Array);
KCtr++;
if (KCtr == K) {
result = *o;
residx = o - Array;
break;
}
}
printf(" full: FINAL result=%d residx=%ld\n",result,residx);
return result;
}
void
test(int *Array,long siz)
{
int *ArrEnd = &Array[siz / sizeof(int)];
int oval;
int fval;
if (sepflg)
printf("\n");
sepflg = 1;
printf("Array%d:",tstno);
for (int *ptr = Array; ptr < ArrEnd; ++ptr)
printf(" %4d",*ptr);
printf("\n");
oval = orig(Array,ArrEnd);
printf("\n");
fval = full(Array,ArrEnd);
printf("\n");
printf(" test: %s orig=%d full=%d\n",
(oval == fval) ? "PASS" : "FAIL",oval,fval);
++tstno;
}
int
main(void)
{
test(Array0,sizeof(Array0));
test(Array1,sizeof(Array1));
test(Array2,sizeof(Array2));
test(Array3,sizeof(Array3));
test(Array4,sizeof(Array4));
test(Array5,sizeof(Array5));
test(Array6,sizeof(Array6));
return 0;
}
程序输出如下：
Array0: 1 2 1 3 4
orig: MATCH value=2 index=1
orig: MATCH value=3 index=3
orig: MATCH value=4 index=4
orig: FINAL result=4 residx=4
full: MATCH value=2 index=1
full: MATCH value=3 index=3
full: MATCH value=4 index=4
full: FINAL result=4 residx=4
test: PASS orig=4 full=4
Array1: 1 2 4 8 16 32 64 128
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=4 index=2
full: FINAL result=4 residx=2
test: FAIL orig=8 full=4
Array2: 1 2 4 4 8 16 32 64 128
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=4
orig: FINAL result=8 residx=4
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=8 index=4
full: FINAL result=8 residx=4
test: PASS orig=8 full=8
Array3: 1 2 4 8 16 32 64 128 2
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=4 index=2
full: MATCH value=8 index=3
full: FINAL result=8 residx=3
test: PASS orig=8 full=8
Array4: 1 2 4 8 16 32 64 128 2 4
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=8 index=3
full: MATCH value=16 index=4
full: FINAL result=16 residx=4
test: FAIL orig=8 full=16
Array5: 1 2 3 4 5 6
orig: MATCH value=2 index=1
orig: MATCH value=3 index=2
orig: MATCH value=4 index=3
orig: FINAL result=4 residx=3
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=3 index=2
full: FINAL result=3 residx=2
test: FAIL orig=4 full=3
Array6: 1 2 3 4 5 6 1 3
orig: MATCH value=2 index=1
orig: MATCH value=3 index=2
orig: MATCH value=4 index=3
orig: FINAL result=4 residx=3
full: MATCH value=2 index=1
full: MATCH value=4 index=3
full: MATCH value=5 index=4
full: FINAL result=5 residx=4
test: FAIL orig=4 full=5
说明这两个问题的最简单测试是 Array5 和 Array6
对应的asm代码如下：
.data
Array: .word 1, 2, 3, 4, 5, 6, 1, 3
ArrEnd:
K: .word 3
.text
.globl main
# s0 for K
# s1 for result
# t0 for o (as pointer)
# t1 for i (as pointer)
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t6 for counter to reach K (i.e. KCtr?)
main:
lw $s0,K # K
li $t6,0 # KCtr = 0
la $t2,ArrEnd # point to end of array
la $t0,Array # o = &Array[0]
li $s1,-1 # get fail value
b outstart
outerloop:
addiu $t0,$t0,4 # advance o [as pointer]
outstart:
bgeu $t0,$t2,finish # o < ArrEnd? if no, fly
lw $t3,0($t0) # get Array[o]
la $t1,Array # i = &Array[0]
innerloop:
lw $t4,0($t1) # get Array[i]
beq $t1,$t0,innernext # o == i? if yes, skip test
beq $t3,$t4,outerloop # Array[o] == Array[i]? if yes, not unique
innernext:
addiu $t1,$t1,4 # advance array pointer for i
bltu $t1,$t2,innerloop # at end? if no, loop
# current array value is unique
addi $t6,$t6,1 # KCtr++
bne $t6,$s0,outerloop # KCtr == K? if no, wait for next unique
lw $s1,0($t0) # get better result -- no need to loop more
finish:
li $v0,1
move $a0,$s1
syscall
li $v0,10
syscall
我正在尝试编写与下面的 C 代码等效的 MIPS。
int arrayData[5] = { 1,2,1,3,4 };
int K = 3;
int KCtr = 0;
int result;
bool isUnique;
for (int o = 1; o < 5; o++)
{
isUnique = true;
for (int i = 0; i < o; i++)
{
if (arrayData[o] == arrayData[i])
{
isUnique = false;
break; // goto outer loop
}
}
if (isUnique)
{
KCtr++;
}
if (KCtr==K)
{
result = arrayData[o];
}
}
我想用下面的代码将结果存储在 $s1 中。
.data
Array: .word 1, 2, 4, 8, 16, 32, 64, 128
sze : .word 8
K : .word 3
.text
.globl main
main: lw $s0,K([=11=]) # K
addi $t0,$zero,0 # index for outer loop
addi $t1,$zero,0 # index for inner loop
lw $t2,sze([=11=])
lw $s1,Array([=11=])
addi $t6,$zero,0
#addi $t7,$zero,1
#t3 for array[o]
#t4 for array[i]
#t5 for unique flag
#t6 for counter to reach K
#t7 for storing 1
outerloop:
beq $t0,$t2,finish
lw $t3,Array($t0)
addi $t5,$zero,0
innerloop:
lw $t4,Array($t1)
bne $t3,$t4,else
addi $t5,$zero,1
else:
checkifunique:
beq $t5,$t7,isnotuniquebypass
addi $t6,$zero,1
isnotuniquebypass:
addi $t1,$t1,4
blt $t1,$t0,innerloop
bne $t6,$s0,notreachedKbypass
lw $s1,Array($t0)
notreachedKbypass:
addi $t0,$t0,4
b outerloop
finish:
li $v0,10
syscall
虽然我希望在 $s1 寄存器中看到 8，但我得到了 1。我的汇编代码有什么问题？
有些事情是错误的。
您的 C 代码不完整。通过检查您的 asm 代码，我能够将缺失的内容添加到 C 代码中。
您没有正确设置一些寄存器。
您还比较了数组偏移量（递增 4 的迭代变量）与数组 index/count，因此比较不起作用。
您将 KCtr 的寄存器设置为 1，而不是执行 KCtr++
我创建了三个示例：固定的 C 代码，您的 asm 的注释版本显示了 some/most 个错误。并且，一个清理、重构和工作的版本。
这是 C 代码：
#include <stdio.h>
#if 0
int Array[] = { 1, 2, 1, 3, 4 };
#else
int Array[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
#endif
int
main(void)
{
int result;
int K = 3;
int KCtr = 0;
int count = sizeof(Array) / sizeof(Array[0]);
int uniqflg;
result = -1;
for (int o = 1; o < count; o++) {
uniqflg = 1;
for (int i = 0; i < o; i++) {
if (Array[o] == Array[i]) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
KCtr++;
if (KCtr == K) {
result = Array[o];
}
}
printf("result=%d\n",result);
return result;
}
这是注释版本：
.data
Array: .word 1,2,4,8,16,32,64,128
sze :
K :
.text
.globl main
# s1 for result
# t0 for o
# t1 for i
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t5 for unique flag
# t6 for counter to reach K (i.e. KCtr?)
# t7 for storing 1
main:
lw $s0,K([=11=]) # K
addi $t0,$zero,0 # index for outer loop
# NOTE/BUG: this is misplaced it needs to be moved to just above innerloop
addi $t1,$zero,0 # index for inner loop
lw $t2,sze([=11=]) # get array count
lw $s1,Array([=11=]) # result = Array[0]
addi $t6,$zero,0 # KCtr = 0
# NOTE/BUG: this was commented out:
addi $t7,$zero,1
outerloop:
# NOTE/BUG: based on the increment by 4 to $t0 below, this is comparing an
# offset against a count
beq $t0,$t2,finish # o < count? if no, fly
lw $t3,Array($t0) # get Array[o]
addi $t5,$zero,0 # uniqflg = 0
innerloop:
lw $t4,Array($t1) # get Array[i]
bne $t3,$t4,inner_neq # Array[o] == Array[i]? if no, fly
# NOTE/BUG: this is just setting one (i.e. KCtr = 1 instead of KCtr++)
addi $t5,$zero,1 # uniqflg = 1
inner_neq:
checkifunique:
beq $t5,$t7,notuniq # ???
addi $t6,$zero,1
notuniq:
addi $t1,$t1,4 # advance array offset
# NOTE/BUG: this compares an array offset against an index
blt $t1,$t0,innerloop # at end? if no, loop
bne $t6,$s0,inner_next # KCtr == K? if no, interate
lw $s1,Array($t0) # get better result
inner_next:
addi $t0,$t0,4 # advance o [as offset]
b outerloop
finish:
li $v0,10
syscall
这是重构后的版本。它与您的有所不同，因为为了使其正常工作，我对其进行了一些简化。它还使用指针而不是索引或偏移量来访问数组。还要注意，一旦KCtr == K，就不需要继续循环了。
.data
Array: .word 1,2,4,8,16,32,64,128
ArrEnd:
K: .word 3
.text
.globl main
# s0 for K
# s1 for result
# t0 for o (as pointer)
# t1 for i (as pointer)
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t6 for counter to reach K (i.e. KCtr?)
main:
lw $s0,K # K
li $t6,0 # KCtr = 0
la $t2,ArrEnd # point to end of array
la $t0,Array # o = &Array[0]
lw $s1,0($t0) # result = Array[0]
outerloop:
addiu $t0,$t0,4 # advance o [as pointer]
bgeu $t0,$t2,finish # o < ArrEnd? if no, fly
lw $t3,0($t0) # get Array[o]
la $t1,Array # i = &Array[0]
innerloop:
lw $t4,0($t1) # get Array[i]
beq $t3,$t4,outerloop # Array[o] == Array[i]? if yes, not unique
addiu $t1,$t1,4 # advance array pointer for i
bltu $t1,$t0,innerloop # at end? if no, loop
# current array value is unique
addi $t6,$t6,1 # KCtr++
bne $t6,$s0,outerloop # KCtr == K? if no, wait for next unique
lw $s1,0($t0) # get better result -- no need to loop more
finish:
li $v0,1
move $a0,$s1
syscall
li $v0,10
syscall
更新：
Your code seems to be working in spim. But I didn't understand "ArrayEnd". There is no value set for it,but it works. How ?
ArrEnd 是某种 "trick"。是Array+1的最后一个元素的地址。也就是说，在C中，如果我们有int Array[5]，那么ArrEnd就是&Array[5]。
就像在 C 中一样，我们可以选择如何遍历数组。我们可以使用索引并执行：Array[i]。或者，我们可以使用 int * 指针。在 asm 中，我们可以使用从数组开始的偏移量（即 index << 2）。
让我们将 C 程序重新编码为 仅 使用指针 [而不是索引] 遍历数组。这在 C 代码中不常使用，但它对 asm 很方便。以下实际上是我的第二个 asm 示例所做的更准确的 C 代码表示：
#include <stdio.h>
#if 0
int Array[] = { 1, 2, 1, 3, 4 };
#else
int Array[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
#endif
int
main(void)
{
int result;
int K = 3;
int KCtr = 0;
int *ArrEnd = &Array[sizeof(Array) / sizeof(Array[0])];
int uniqflg;
result = -1;
for (int *o = &Array[1]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < o; i++) {
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
KCtr++;
if (KCtr == K) {
result = *o;
break;
}
}
printf("result=%d\n",result);
return result;
}
以下是 ArrEnd 的一些惯用用法：
la $s0,Array # get array address
la $s1,ArrEnd # address of array end [one past last]
subu $s2,$s1,$s0 # get byte length of array
srl $s3,$s2,2 # get array count
现在我们有了这些值，我们可以通过上述三种方法中的任何一种来遍历数组。使用偏移版本或指针版本通常可以更有效。
要了解 ArrEnd 使事情变得多么简单，请注释掉较大的数组并从 C 代码中添加较短的数组。 ArrEnd 技巧将自动调整 而无需 需要手动计算 Array
更新#2：
我可能对此有误，但进一步思考，为了满足问题标题的要求，C代码[以及因此asm]可能需要更改。
我认为内部循环在查找重复项时必须扫描 整个 数组 [跳过 i == o 所在的元素]。否则可能会误报。
还有，看来原文从来不认为index 0元素是唯一的，即使是。这是因为 o 循环从索引 1 开始。
我创建了两种算法。原文如上。还有一个进行全面扫描的。我还添加了更多测试用例来说明我正在考虑的问题。
测试程序如下：
#include <stdio.h>
int Array0[] = { 1, 2, 1, 3, 4 };
int Array1[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
int Array2[] = { 1, 2, 4, 4, 8, 16, 32, 64, 128 };
int Array3[] = { 1, 2, 4, 8, 16, 32, 64, 128, 2 };
int Array4[] = { 1, 2, 4, 8, 16, 32, 64, 128, 2, 4 };
int Array5[] = { 1, 2, 3, 4, 5, 6 };
int Array6[] = { 1, 2, 3, 4, 5, 6, 1, 3 };
int K = 3;
int sepflg;
int tstno;
int
orig(int *Array,int *ArrEnd)
{
int result;
long residx;
int KCtr = 0;
int uniqflg;
result = -1;
residx = -1;
for (int *o = &Array[1]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < o; i++) {
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
printf(" orig: MATCH value=%d index=%ld\n",*o,o - Array);
KCtr++;
if (KCtr == K) {
result = *o;
residx = o - Array;
break;
}
}
printf(" orig: FINAL result=%d residx=%ld\n",result,residx);
return result;
}
int
full(int *Array,int *ArrEnd)
{
int result;
long residx;
int KCtr = 0;
int uniqflg;
result = -1;
residx = -1;
for (int *o = &Array[0]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < ArrEnd; i++) {
if (o == i)
continue;
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
printf(" full: MATCH value=%d index=%ld\n",*o,o - Array);
KCtr++;
if (KCtr == K) {
result = *o;
residx = o - Array;
break;
}
}
printf(" full: FINAL result=%d residx=%ld\n",result,residx);
return result;
}
void
test(int *Array,long siz)
{
int *ArrEnd = &Array[siz / sizeof(int)];
int oval;
int fval;
if (sepflg)
printf("\n");
sepflg = 1;
printf("Array%d:",tstno);
for (int *ptr = Array; ptr < ArrEnd; ++ptr)
printf(" %4d",*ptr);
printf("\n");
oval = orig(Array,ArrEnd);
printf("\n");
fval = full(Array,ArrEnd);
printf("\n");
printf(" test: %s orig=%d full=%d\n",
(oval == fval) ? "PASS" : "FAIL",oval,fval);
++tstno;
}
int
main(void)
{
test(Array0,sizeof(Array0));
test(Array1,sizeof(Array1));
test(Array2,sizeof(Array2));
test(Array3,sizeof(Array3));
test(Array4,sizeof(Array4));
test(Array5,sizeof(Array5));
test(Array6,sizeof(Array6));
return 0;
}
程序输出如下：
Array0: 1 2 1 3 4
orig: MATCH value=2 index=1
orig: MATCH value=3 index=3
orig: MATCH value=4 index=4
orig: FINAL result=4 residx=4
full: MATCH value=2 index=1
full: MATCH value=3 index=3
full: MATCH value=4 index=4
full: FINAL result=4 residx=4
test: PASS orig=4 full=4
Array1: 1 2 4 8 16 32 64 128
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=4 index=2
full: FINAL result=4 residx=2
test: FAIL orig=8 full=4
Array2: 1 2 4 4 8 16 32 64 128
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=4
orig: FINAL result=8 residx=4
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=8 index=4
full: FINAL result=8 residx=4
test: PASS orig=8 full=8
Array3: 1 2 4 8 16 32 64 128 2
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=4 index=2
full: MATCH value=8 index=3
full: FINAL result=8 residx=3
test: PASS orig=8 full=8
Array4: 1 2 4 8 16 32 64 128 2 4
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=8 index=3
full: MATCH value=16 index=4
full: FINAL result=16 residx=4
test: FAIL orig=8 full=16
Array5: 1 2 3 4 5 6
orig: MATCH value=2 index=1
orig: MATCH value=3 index=2
orig: MATCH value=4 index=3
orig: FINAL result=4 residx=3
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=3 index=2
full: FINAL result=3 residx=2
test: FAIL orig=4 full=3
Array6: 1 2 3 4 5 6 1 3
orig: MATCH value=2 index=1
orig: MATCH value=3 index=2
orig: MATCH value=4 index=3
orig: FINAL result=4 residx=3
full: MATCH value=2 index=1
full: MATCH value=4 index=3
full: MATCH value=5 index=4
full: FINAL result=5 residx=4
test: FAIL orig=4 full=5
说明这两个问题的最简单测试是 Array5 和 Array6
对应的asm代码如下：
.data
Array: .word 1, 2, 3, 4, 5, 6, 1, 3
ArrEnd:
K: .word 3
.text
.globl main
# s0 for K
# s1 for result
# t0 for o (as pointer)
# t1 for i (as pointer)
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t6 for counter to reach K (i.e. KCtr?)
main:
lw $s0,K # K
li $t6,0 # KCtr = 0
la $t2,ArrEnd # point to end of array
la $t0,Array # o = &Array[0]
li $s1,-1 # get fail value
b outstart
outerloop:
addiu $t0,$t0,4 # advance o [as pointer]
outstart:
bgeu $t0,$t2,finish # o < ArrEnd? if no, fly
lw $t3,0($t0) # get Array[o]
la $t1,Array # i = &Array[0]
innerloop:
lw $t4,0($t1) # get Array[i]
beq $t1,$t0,innernext # o == i? if yes, skip test
beq $t3,$t4,outerloop # Array[o] == Array[i]? if yes, not unique
innernext:
addiu $t1,$t1,4 # advance array pointer for i
bltu $t1,$t2,innerloop # at end? if no, loop
# current array value is unique
addi $t6,$t6,1 # KCtr++
bne $t6,$s0,outerloop # KCtr == K? if no, wait for next unique
lw $s1,0($t0) # get better result -- no need to loop more
finish:
li $v0,1
move $a0,$s1
syscall
li $v0,10
syscall