ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Мера неупорядоченности линейного массива и некоторые вопросы
3 сообщений из 53, страница 3 из 3
  3  все
Мера неупорядоченности линейного массива и некоторые вопросы
    #39080896
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryПрочитал статью Тадао Такаока(учёный не так давно решивший новым способом проблему Maimum subarray sum) о новых мерах энтропии неупорядоченного массива, захотел посмотреть алгоритмы работы со старыми. Информации особой по реализации не нашёл, потому решил самостоятельно этим заняться
Там критично именно так считать? Может взять за основу что-нибудь близкое, но легче считаемое? Например получить сумму смещений вперед после сортировки.
Например:
1,5,3,2,4 исходный
1,2,3,4,5 отсортированный
тут только 5 уехало на 3 вперед, т.е. итого 3.
Это быстрее считается.

там вообще не так считают и не совсем про это, больше теорем)) Мне захотелось посчитать меру таким образом(скорее всего так тоже считают, и мы тут не первооткрыватели ), но аналогичных расчётов я не нашёл в сети. В России этим очевидно никто не занимается, а зарубежных статей не много. Тем более все статьи из журналов SIAM платные. Потому 'погуглить'(как мне обычно советует Анатолий) не получилось
...
Рейтинг: 0 / 0
20.10.2015, 10:02
| Ответить | Цитировать | Написать  
Мера неупорядоченности линейного массива и некоторые вопросы
    #39080969
mcureenab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mcureenab
Участник
SashaMercuryПодскажите пожалуйста в чём главные ошибки по реализации программы в оос. И может быть у кого-то есть ещё соображения по реализации алгоритма (с линейной скоростью или с лучшей организацией дерева за исключением вопросов балансировки(на данный момент))

PS
Я ещё не прочитал статью о различиях между malloc и new потому пока использую malloc, вы в своих программах на С++ используете только new ?

Память лучше выделять большими блоками, чтобы кучу лишний раз не дергать и расход меньше:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
--
const size_t BLOCK_SIZE = 1024;
struct node * g_block_nodes;
size_t g_block_free = 0;

...


if(!block_free)
{
    block_nodes = calloc(sizeof(struct node[BLOCK_SIZE]));
    block_free = BLOCK_SIZE;
}
struct node * l_node = block_nodes[--block_free];
...
Рейтинг: 0 / 0
20.10.2015, 10:49
| Ответить | Цитировать | Написать  
Мера неупорядоченности линейного массива и некоторые вопросы
    #39081500
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima Tkealon(Ruslan)в индексе будут позиции элементов в исходном массиве
Код: plaintext
1.
2.
3.
Element:0  position:5000  smaller count:0  greater count:49999
Element:1  position:5001  smaller count:1  greater count:49998
Element:2  position:9452  smaller count:2  greater count:49997
...

Ты не то посчитал. Надо не сколько всего элементов больше конкретного, а сколько больших элементов между началом и конкретным. Затем сложить полученное.

У меня первая мысль была что можно отсортировать, а затем как-то в один проход посчитать используя только 2 индекса элемента: в изначальном массиве и отсортированном. Но запнулся на такой последовательности 1,5,3,2,4. Результат у нее 0+0+1+2+1.

ЗЫ про С/С++ форум. Паскаль запустить негде. Тут заготовка теста с перебором 18274025
ну тогда с весо-балансированным деревом легко решается
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
program TestWeightBalance;

uses GUtils,OrdSets;

const
  TEST_SIZE = 50000;

type
  TValue = integer;
var
  Arr: array of TValue;


  procedure Init;
  var
    i: integer;
    tmp: TValue;
    r: integer;
  begin
    for i := 0 to TEST_SIZE - 1 do
      arr[i] := i;
    // Перемешиваем
    r := 54323; // ГСЧ с постоянной последовательстью
    for i := 0 to TEST_SIZE - 1 do
    begin
      repeat
        r := (r * 12347 + 1) mod TEST_SIZE;
      until (r >= 0);

      tmp := arr[i];
      arr[i] := arr[r];
      arr[r] := tmp;
    end;
  end;
type
  TUp=Specialize GUp<TValue>;
  TValueSet=specialize OrdSetWB <TValue,TUp>;

var

  i,p: integer;
  vs: TValueSet;
begin
  SetLength(Arr, TEST_SIZE);
  Init;
  vs:=TValueSet.Create;
  try
    for i:=0 to TEST_SIZE-1 do begin
      vs.Insert(arr[i]);
      p := vs.KeyIndex(arr[i]);
      writeln('< Count:', p, '  >Count:', i - p);
    end;
  finally
    vs.Free;
  end;
end.



реп с либами здесь


компилируется только под Lazarus (fpc)
...
Рейтинг: 0 / 0
20.10.2015, 16:24
| Ответить | Цитировать | Написать  
3 сообщений из 53, страница 3 из 3
  3  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Мера неупорядоченности линейного массива и некоторые вопросы
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]