グラフを描き続ける(SQL)


SELECT d,RPAD('',20*d/m,'*') n FROM dat, (SELECT MAX(d) m FROM dat) tmp;

MySQLの場合

CREATE TABLE dat (d INT);
INSERT INTO dat (d) VALUES (2),(5),(9);
SELECT d,RPAD('',20*d/m,'*') n FROM dat, (SELECT MAX(d) m FROM dat) tmp;
DROP TABLE dat;
+------+----------------------+
| d    | n                    |
+------+----------------------+
|    2 | ****                 |
|    5 | ***********          |
|    9 | ******************** |
+------+----------------------+

この書き方はOracleのマニュアルにも載ってるし、別に新しくないね(MySQL限定ならREPEATでもいい)。
やっていることは、「Excelのグラフを見直す」と同じ。OracleだとINSERTが面倒になるのかな

{2,5,9}のような入力をパースするのもいいんだけど、SQLを使う場面で役に立つことはないでしょう。やりすぎだし

キミならどう書く 2.0 – ROUND 3 –

コラッツ予想(MySQL編)


WHILE EXISTS (SELECT * FROM integers WHERE f!=1) DO
  UPDATE integers SET f=IF(MOD(f,2)=0,f/2,3*f+1),g=g+1 WHERE f!=1;
END WHILE;
SELECT n h FROM integers WHERE g=(SELECT max(g) FROM integers);

主記憶が足りなくなるかもという向きには、データベースがおすすめ(まじめな人はBIGINTにしてね)。{n,f,g}を格納するテーブルを作っておいて、
あとは言われたとおりにf=1になるまで計算、gの値が最大になる行のnを問い合わせればいい

MySQLなら全体は次のようになる(主記憶を気にしないなら、CREATE TABLE文の最後にTYPE=HEAPをつけて速くできる)

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (n INT PRIMARY KEY,f INT NOT NULL,g INT DEFAULT 0 NOT NULL,KEY(f))//

DROP PROCEDURE IF EXISTS collatz//
CREATE PROCEDURE collatz(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 1;
  TRUNCATE TABLE integers;
  SET i=1;
  WHILE i<maxNum+1 DO
    INSERT INTO integers (n,f) VALUES (i,i);
    SET i=i+1;
  END WHILE;
  
  WHILE EXISTS (SELECT * FROM integers WHERE f!=1) DO
    UPDATE integers SET f=IF(MOD(f,2)=0,f/2,3*f+1),g=g+1 WHERE f!=1;
  END WHILE;
  
  SELECT n h FROM integers WHERE g=(SELECT max(g) FROM integers);
END;//

CALL collatz(100)//
+----+
| h  |
+----+
| 97 |
+----+

途中の計算結果を利用したいなら、主要部を次のように変更

UPDATE integers a,integers b SET a.f=1,a.g=a.g+b.g WHERE a.f!=1 AND a.f=b.n AND b.f=1;
UPDATE integers SET f=IF(MOD(f,2)=0,f/2,3*f+1),g=g+1 WHERE f!=1;

これでかなり速くなる。欲を出して、途中の計算をすべて記憶しておこうとすると逆効果。「テーブルにないfの値が出てきたら、それをテーブルのnに追加し、計算はそっちだけにする」という戦略で解くのが下(calは、fを計算するかどうかを指示するフラグ)

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (
  n INT PRIMARY KEY,
  f INT NOT NULL,
  g INT DEFAULT 0 NOT NULL,
  cal BOOL DEFAULT 1 NOT NULL,
  KEY(f),
  KEY(cal)
)//

DROP PROCEDURE IF EXISTS collatz//
CREATE PROCEDURE collatz(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 1;
  TRUNCATE TABLE integers;
  SET i=1;
  WHILE i<maxNum+1 DO
    INSERT INTO integers (n,f) VALUES (i,i);
    SET i=i+1;
  END WHILE;
  
  WHILE EXISTS (SELECT * FROM integers WHERE f!=1) DO
    UPDATE integers a,integers b SET a.f=1,a.g=a.g+b.g WHERE a.f!=1 AND a.f=b.n AND b.f=1;
    INSERT INTO integers (n,f) SELECT f n,f FROM integers a WHERE a.f!=1 AND NOT EXISTS (SELECT * FROM integers b WHERE a.f=b.n);
    UPDATE integers a,integers b SET a.cal=0 WHERE a.f=b.n AND a.g!=0 AND b.g=0;
    UPDATE integers SET f=IF(MOD(f,2)=0,f/2,3*f+1),g=g+1 WHERE f!=1 AND cal!=0;
  END WHILE;
  
  SELECT n h FROM integers WHERE g=(SELECT max(g) FROM integers);
END;//

CALL collatz(100)//
+----+
| h  |
+----+
| 97 |
+----+

SELECT COUNT(n) FROM integers//
+----------+
| COUNT(n) |
+----------+
|      251 |
+----------+

キミならどう書く 2.0 – ROUND 2 –

100までの整数から素数を列挙せよ(SQL編)


キミならどう書く 2.0 – ROUND 1 –

「欲しいものを書くだけでいい」というのがSQLのいいところ。この場合は「約数をちょうど2つ持つ整数」と書けばいい。エラトステネスの篩いを試みたりしてはいけない。(そういう意味ではPrologでもいいのだけれど、文法を思い出せない。)

-- 0から9までの数を入れるテーブル
create table nums (i integer);

-- 0から9までの数を入れる
insert into nums (i) values (0), (1), (2), (3), (4), (5), (6), (7), (8), (9);

-- 0から99までの数を入れるテーブル(100は素数でない)
drop table if exists integers;
create table integers
  select 10*a.i+b.i as n
  from nums as a, nums as b
  order by n;

-- 素数を表示する
select n prime from(
  select x.n, count(distinct d.n) c
  from integers x,integers d
  where mod(x.n,d.n)=0 and d.n<=x.n
  group by x.n) tmp
where c=2
order by prime;

以上


以下は古いバージョン(いろいろやりすぎ)。

SELECT n prime FROM(
  SELECT x.n,COUNT(DISTINCT d.n) c
    FROM integers x,integers d
    WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
    GROUP BY x.n) tmp
  WHERE c=2;

あらかじめ整数をテーブルに入れておくという準備が必要で、Oracleならこんな感じか。

DROP TABLE integers;
CREATE TABLE integers (n INT NOT NULL);

DECLARE
  maxNum INT:=100;
  i INT:=1;
BEGIN
  EXECUTE IMMEDIATE 'TRUNCATE TABLE integers';
  WHILE i<maxNum LOOP
    INSERT INTO integers (n) VALUES (i);
    i:=i+1;
  END LOOP;
END;
/
SELECT n prime FROM(
  SELECT x.n,COUNT(DISTINCT d.n) c
    FROM integers x,integers d
    WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
    GROUP BY x.n) tmp
  WHERE c=2;

SELECT文を直接書けないからPL/SQLはあまり好きではないんだけど、
無理矢理PROCEDUREにするなら、こんな感じか。

CREATE OR REPLACE PROCEDURE primes (maxNum INT) AS
  i INT:=1;
  CURSOR cur IS
    SELECT n prime FROM(
      SELECT x.n,COUNT(DISTINCT d.n) c
        FROM integers x,integers d
        WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
        GROUP BY x.n) tmp
      WHERE c=2;
BEGIN
  EXECUTE IMMEDIATE 'TRUNCATE TABLE integers';
  WHILE i<maxNum LOOP
    INSERT INTO integers (n) VALUES (i);
    i:=i+1;
  END LOOP;
  
  FOR item IN cur
  LOOP
    DBMS_OUTPUT.PUT_LINE(item.prime);
  END LOOP;
END;
/
CALL primes(100);

Version 5になってやっと使えるようになったMySQLのストアド・プロシージャを使うなら。

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (n INT)//

DROP PROCEDURE IF EXISTS primes//
CREATE PROCEDURE primes(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 1;
  TRUNCATE table integers;
  WHILE i<maxNum DO
    INSERT INTO integers (n) VALUES (i);
    SET i=i+1;
  END WHILE;
  
  SELECT n prime FROM(
    SELECT x.n,COUNT(DISTINCT d.n) c
      FROM integers x,integers d
      WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
      GROUP BY x.n) tmp
    WHERE c=2;
END;//

CALL primes(100)//

追記:エラトステネスの篩いね、そりゃあ、このほうが速いよ。

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (
  n INT PRIMARY KEY,
  flag INT DEFAULT 0 NOT NULL,
  KEY(flag)
)//

DROP TABLE IF EXISTS results//
CREATE TABLE results (prime INT PRIMARY KEY)//

DROP PROCEDURE IF EXISTS primes//
CREATE PROCEDURE primes(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 2;
  TRUNCATE table integers;
  WHILE i<maxNum DO
    INSERT INTO integers (n) VALUES (i);
    SET i=i+1;
  END WHILE;
  
  WHILE EXISTS (SELECT * FROM integers WHERE flag=0) DO
    INSERT INTO results (prime) SELECT n FROM integers WHERE flag=0 LIMIT 1;
    UPDATE integers JOIN (SELECT MAX(prime) p FROM results) tmp SET flag=1 WHERE MOD(n,p)=0;
  END WHILE;
  
  SELECT prime FROM results;
END;//

CALL primes(100)//